题目大意
在 n*n 的不规则的棋盘上摆放 k 枚棋子, 要求每行和每列上只能有一枚棋子.
思路
和八皇后问题类似, 只不过这个问题不一定是一行摆放一个. 因此 dfs 的时候要多用一个参数来表示当前搜索的行数.
题解
- #include <iostream>
- #include <cstring>
- using namespace std;
- int n,k,ans;
- char a[10][10];
- bool vis[10];
- void dfs(int num, int row)
- {
- if(num>= k)
- {
- ans++; // 放完所有的棋子, 答案数 + 1
- return;
- }
- for(int i = row; i <n; i++)
- {
- for(int j = 0; j < n; j++)
- {
- if(!vis[j] && a[i][j] == '#')
- {
- vis[j] = true; // 在 [i][j] 位置放一枚棋子
- dfs(num+1, i+1); // 搜索下一行能放的位置
- vis[j] = false; // 回溯到上一行的状态
- }
- }
- }
- }
- int main(){
- #ifdef debug
- freopen("test.txt","r",stdin);
- #endif
- while(cin>> n>> k)
- {
- if(n == -1 && k == -1) return 0;
- ans = 0;
- memset(vis, false, sizeof(vis));
- memset(a, 0, sizeof(a));
- for(int i = 0; i <n; i++)
- {
- for(int j = 0; j < n; j++)
- {
- cin>> a[i][j];
- }
- }
- dfs(0,0);
- cout << ans << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2927178.html