3966 - E. n皇后摆放问题
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。在n×n格的棋盘上，已经摆放好其它的一些棋子，皇后与皇后之间如果有棋子，就不能相互攻击，求出在n×n的棋盘上可以摆放最多的相互不能攻击的皇后数。
Input
首先输入n（n<=4），然后输入n×n的棋盘，”X”表示已经摆放了的棋子，”.”表示棋盘空位。
Output
输出最多能摆放的皇后数。
Examples
Input
4 .X.. .... XX.. .... 2 XX .X 3 .X. X.X .X. 3 ... .XX .XX 4 .... .... .... ....
Output
4 1 2 2 4
Solution C++
//回溯法 #include<iostream> #include<string> using namespace std; char map[4][4]; int best, n; int place(int row, int col) { int i; for (i = col - 1; i >= 0; i--){ //向左方向 if (map[row][i] == 'X') break; if (map[row][i] == '1') return 0; } int j = col; for (i = row - 1; i >= 0; i--){ //左上方向 j--; if (j<0) break; if (map[i][j] == 'X') break; if (map[i][j] == '1') return 0; } j = col; for (i = row - 1; i >= 0; i--){ //右上方向 j++; if (j>n - 1) break; if (map[i][j] == 'X') break; if (map[i][j] == '1') return 0; } for (i = row - 1; i >= 0; i--){ //向上方向 if (map[i][col] == 'X') break; if (map[i][col] == '1') return 0; } return 1; } void Backtrack(int t, int sum) { if (t >= n*n){ if (sum>best) best = sum; return; } int col, row; row = t / n; col = t%n; if (map[row][col] == '.'){ if (place(row, col)) { map[row][col] = '1'; //放炮后，递归 Backtrack(t + 1, sum + 1); map[row][col] = '.';//不放炮，递归 } } Backtrack(t + 1, sum); } int main() { while (cin >> n) { int i; int j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) cin >> map[i][j]; best = 0; Backtrack(0, 0); cout << best << endl; } return 0; }