P1274题dfs函数为什么跑到一半不跑了
  • 板块灌水区
  • 楼主zrt090604
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/8/24 16:07
  • 上次更新2023/10/27 13:52:06
查看原帖
P1274题dfs函数为什么跑到一半不跑了
459188
zrt090604楼主2022/8/24 16:07
#include<bits/stdc++.h>
using namespace std;
int x, y, r = 1, c = 1, ans[5][5];
bool vis[17];
void print() {
	for(int i = 1;i <= 4;++i) {
		for(int j = 1;j <= 4;++j)
			printf("%d ", ans[i][j]);
		puts("");
	}
	puts("");
	return;
}
bool row(int a, int b, int v) {
	if(b==4) return ans[a][1]+ans[a][2]+ans[a][3]+v==34;
	if(ans[a][1]+ans[a][2]+ans[a][3]+v <= 34) return true;
	return false;
}
bool col(int a, int b, int v) {
	if(a==4) return ans[1][a]+ans[2][a]+ans[3][a]+v==34;
	if(ans[1][a]+ans[2][a]+ans[3][a]+v <= 34) return true;
	return false;
}
bool xl(int a, int b, int v) {
	if(a==4 && b==4) return ans[1][1]+ans[2][2]+ans[3][3]+v==34;
	if(ans[1][1]+ans[2][2]+ans[3][3]+v <= 34) return true;
	return false;
}
bool xr(int a, int b, int v) {
	if(a==4) return ans[1][4]+ans[2][3]+ans[3][2]+v==34;
	if(ans[1][4]+ans[2][3]+ans[3][2] <= 34) return true;
	return false;
}
bool mid(int a, int b, int v) {
	if(a>3 || a==3&&b>=3) return ans[2][2]+ans[2][3]+ans[3][2]+v==34;
	if(ans[2][2]+ans[2][3]+ans[3][2]+v <= 34) return true;
	return false;
}
void dfs(int k) {
	print();
	if(r==x && c==y) {y==4 ? ++r, c=1 : ++c; dfs(k+1);}
	if(k == 17) {
		if(ans[1][1]+ans[1][4]+ans[4][1]+ans[4][4] == 34) print();
		return;
	}
	for(int i = 2;i <= 16;++i) {
		if(!vis[i] && row(r, c, i) && col(r, c, i) && xl(r, c, i) && xr(r, c, i) && mid(r, c, i)) {
			ans[r][c] = i;
			vis[i] = true;
			if(c==4) ++r, c=1, dfs(k+1);
			else ++c, dfs(k+1);
			vis[i] = false;
		}
	}
	return;
}
int main () {
	memset(ans, 0, sizeof ans);
	scanf("%d%d", &x, &y);
	ans[x][y] = 1;
	vis[1] = true;
	dfs(1);
	return 0;
}

求助

2022/8/24 16:07
加载中...