棋盘问题（放置棋子）

题目：

题目解析：

在n*n的矩阵内描述棋盘，棋盘的“形状”输入决定，只能在#的位置放棋子，棋子不能同行，不能同列。

思路：

逐行尝试，放完第一行放第二行……每行的#都要尝试，同时用一个数组来标记一列上是否已经存在棋子。相当于每次从第一行的某个#出发，前往下一行的#，直到最后一行或者把棋子放完，有点类似于dfs，用递归最方便：

代码：

#include<iostream>
#include<vector>
#include<string>
using namespace std;int cnt = 0;void placeInRow(int row, int k, int n, vector<string>& board, vector<bool>& cols)
{if (k == 0)//如果棋子已经放完了，方案加1{cnt++;return;}if (row == n)//如果最后一行已经放完了，那么结束return;//尝试在当前行的每个有效位置放置棋子for (int col = 0; col < n; col++){if (board[row][col] == '#' && !cols[col]){cols[col] = true;placeInRow(row + 1, k - 1, n, board, cols);//处理下一行cols[col] = false;//回溯的时候要清理棋子}}//当前行无法放置棋子，直接调到下一行placeInRow(row + 1, k, n, board, cols);
}int main()
{int n, k;while (cin >> n >> k){if (n == -1 && k == -1)break;vector<string> board(n);//棋盘for (int i = 0; i < n; i++)cin >> board[i];//读取棋盘信息cnt = 0;//每一轮重置一次countvector<bool> cols(n, false);//列标记placeInRow(0, k, n, board, cols);cout << cnt << endl;}return 0;
}