本文主要是介绍ZOJ 1002 回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int a[5][5], w[5][5];
int n, ans;bool check(int r, int c)
{int i;if(w[r][c] == 1) return false;for(i = r - 1; i >= 0; i--){if(a[i][c] == 1) return false;if(w[i][c] == 1) break;}for(i = r + 1; i < n; i++){if(a[i][c] == 1) return false;if(w[i][c] == 1) break;}for(i = c - 1; i >= 0; i--){if(a[r][i] == 1) return false;if(w[r][i] == 1) break;}for(i = c + 1; i < n; i++){if(a[r][i] == 1) return false;if(w[r][i] == 1) break;}return true;
}void dfs(int index, int cnt)
{if(index == n * n){ans = max(ans, cnt);return;}if(ans > n * n - index + cnt) return;int r = index / n;int c = index % n;if(check(r, c)){a[r][c] = 1;dfs(index + 1, cnt + 1);a[r][c] = 0;dfs(index + 1, cnt);return;}dfs(index + 1, cnt);
}int main()
{while(scanf("%d",&n)){if(n == 0) break;memset(a, 0, sizeof(a));memset(w, 0, sizeof(w));char str[10];for(int i = 0; i < n; i++){scanf("%s",str);for(int j = 0; j < n; j++)if(str[j] == 'X')w[i][j] = 1;}ans = 0;dfs(0, 0);printf("%d\n",ans);}return 0;
}
这篇关于ZOJ 1002 回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
