DFS | 野生开发者

题目描述
给定M根小木棍，每根木棍有各自的长度，能否把它们全部用上来围成一个正方形？其中4≤M≤20，每根木棍的长度是1到10000之间的整数

输入格式
第一行是一个整数T表示测试数据的组数。对于每组测试数据，输入一行，包含M+1个整数，第一个整数表示M，接下来M个整数表示M个木棍的长度

输出格式
对于每组数据一行，如果能够围成正方形输出“yes” 否则输出“no”

输入输出样例

输入

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

输出

1
2
3

yes
no
yes

Solution

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int len[25],v[25],m,l;

bool dfs(int p,int g,int d){
	if(d==3) return true;
	for(int i=p; i>=0; i--){
		if(!v[i]){
			v[i]=1;
			int t=g+len[i];
			if(t<l){
				if(dfs(p-1,t,d))
					return true;
			}
			else if(t==l){
				if(dfs(m-1,0,d+1))
					return true;
			}
			else{
				v[i]=0;
			}
		}
	}
	return false;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int sum=0;
		scanf("%d",&m);
		for(int i=0; i<m; i++){
			scanf("%d",&len[i]);
			sum+=len[i];
		}
		sort(len,len+m);
		memset(v,0,sizeof(v));
		l=sum/4;
		if(sum%4!=0 || m<4 || l<len[m-1]) printf("no\n");
		else if(dfs(m-1,0,0)) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

Problem 2

题目描述
小埋会告诉你一盘扫雷，用一个 n*m 的矩阵表示，1 是雷，0 不是雷，请你告诉她这盘扫雷的 3bv 。

周围八格没有“雷”且自身不是“雷”的方格称为“空格”，周围八格有“雷”且自身不是“雷”的方格称为“数字”，由“空格”组成的八连通块称为一个“空”。3bv = 周围八格没有“空格”的“数字”个数 + “空”的个数。

输入格式
第一行有两个整数 n 和 m，代表这盘扫雷是一个 n*m 的矩阵。

后面的 n 行每行有 m 个整数，表示这个矩阵，每个数字为 0 或 1，1 代表是雷，0 代表不是雷。

输出格式
一个整数，代表这盘扫雷的 3bv 。

输入

8 8
0 0 0 1 1 0 0 0 
1 0 0 1 0 0 0 1 
1 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0

输出

Solution

#include <cstdio>
using namespace std;

int a[1000][1000],v[1000][1000],bv3,n,m;
int x[8]={-1,-1,-1,0,0,1,1,1},y[8]={-1,0,1,-1,1,-1,0,1};

bool noBlank(int l,int r){     //周围八格没有“空格”的
	for(int i=0; i<8; i++){
		int ll=l+x[i]; int rr=r+y[i];
		if(ll>=0 && ll<n && rr>=0 && rr<m && !a[ll][rr])
			return 0;
	}
	return 1;
}

void incr(int l,int r){      //让“雷”周围八格中不是“雷”的都增加1
	for(int i=0; i<8; i++){
		int ll=l+x[i]; int rr=r+y[i];
		if(ll>=0 && ll<n && rr>=0 && rr<m && a[ll][rr]!=-1)
			a[ll][rr]++;
	}
}

void dfs(int l,int r){
	for(int i=0; i<8; i++){
		int ll=l+x[i]; int rr=r+y[i];
		if(ll>=0 && ll<n && rr>=0 && rr<m && !a[ll][rr] && !v[ll][rr]){   //判断是否越界，用v判重
			v[ll][rr]=1;
			dfs(ll,rr);
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++){
			scanf("%d",&a[i][j]);
			if(a[i][j])
				a[i][j]=-1;
		}
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			if(a[i][j]==-1)
				incr(i,j);
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++){
			if(a[i][j] && a[i][j]!=-1 && noBlank(i,j))   //周围八格没有“空格”的“数字”的个数
				bv3++;
		}
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++){
			if(!a[i][j] && !v[i][j]){     //“空”的个数
				bv3++;
				dfs(i,j);
			}
		}
	printf("%d\n", bv3);
	return 0;
}

Problem 3

将数字 1…9 填入一个 3×3 的九宫格中，使得格子中每一横行和的值全部相等，每一竖列和的值全部相等。请你计算有多少种填数字的方案。

next_permutation

https://www.cnblogs.com/eudiwffe/p/6260699.html

https://blog.csdn.net/c18219227162/article/details/50301513

#include <cstdio>
#include <algorithm>
using namespace std;

int a[10];

int main(){
    int ans = 0;
    for(int i = 1; i <= 9; i++)
        a[i] = i;
    do{
        if(a[1] + a[2] + a[3] == a[4] + a[5] + a[6]
        && a[4] + a[5] + a[6] == a[7] + a[8] + a[9]
        ){
            if(a[1] + a[4] + a[7] == a[2] + a[5] + a[8]
            && a[2] + a[5] + a[8] == a[3] + a[6] + a[9]
            )
            ans++;
        }
    }while(next_permutation(a + 1, a + 10));
    printf("%d\n", ans);
    return 0;
}
//72

Problem 4

右侧代码是将 6 个整数按照任意顺序组合到一起，计算能组合出的最大数字。

例如：4123，25，66 组合到一起就是 66412325。

请阅读程序补全代码，实现这个功能

#include <stdio.h>
#include <algorithm>

long long test(int a[], int n) {
	long long ret = 0;
	for (int i = 0; i < n; ++i) {
		int tp = a[i];
		int j = 1;
		while(tp) {
			j *= 10;
			tp /= 10;
		}
		ret = ret * j + a[i];
	}
	return ret;
}

long long f(int a[], int k) {
	if (k == 6) {
		return test(a, k);
	}
	long long ret = 0;
	for(int i = k; i < 6; ++i) {
		int t = a[k];
		a[k] = a[i];
		a[i] = t;
		ret = std::max(ret,  f(a, k + 1));
		t = a[k];
		a[k] = a[i];
		a[i] = t;
	}
	return ret;
}

int main() {
	int a[6] = {517, 283, 429, 65, 6566, 32};
	printf("%lld\n", f(a, 0));
	return 0;
}