#include <iostream> #include <vector> #include <cmath> using namespace std; const int N = 300 ; int n; int map[N][N]; // 棋盘，1表示可放，0表示不可放 int black_pos[N] ; // 黑皇后位置，black_pos[i]表示第i行黑皇后的列索引(1-based) int white_pos[N] ; // 白皇后位置 int total_ways = 0; // 检查第cur行的黑皇后是否与之前的黑皇后冲突 bool check_black(int cur) { for (int i = 1; i < cur; ++i) { // 同列 或 同对角线 if (black_pos[i] == black_pos[cur] || abs(i - cur) == abs(black_pos[i] - black_pos[cur])) { return false; } } return true; } // 检查第cur行的白皇后是否与之前的白皇后冲突 bool check_white(int cur) { for (int i = 1; i < cur; ++i) { // 同列 或 同对角线 if (white_pos[i] == white_pos[cur] || abs(i - cur) == abs(white_pos[i] - white_pos[cur])) { return false; } } return true; } // 放置白皇后 void dfs_white(int cur) { if (cur > n) { // 所有白皇后都放置成功，找到一种解法 total_ways++; return; } for (int col = 1; col <= n; ++col) { // 1. 检查该位置是否原本可用 if (map[cur][col] == 0) continue; // 2. 检查该位置是否已经被黑皇后占据 if (black_pos[cur] == col) continue; // 3. 尝试放置 white_pos[cur] = col; // 4. 检查是否与已放置的白皇后冲突 if (check_white(cur)) { dfs_white(cur + 1); } } } // 放置黑皇后 void dfs_black(int cur) { if (cur > n) { // 所有黑皇后放置完毕，开始放置白皇后 dfs_white(1); return; } for (int col = 1; col <= n; ++col) { // 1. 检查该位置是否原本可用 if (map[cur][col] == 0) continue; // 2. 尝试放置黑皇后 black_pos[cur] = col; // 3. 检查是否与已放置的黑皇后冲突 if (check_black(cur)) { dfs_black(cur + 1); } } } int main() { // 优化IO ios::sync_with_stdio(false); cin.tie(NULL); if (!(cin >> n)) return 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { cin >> map[i][j]; } } // 从第1行开始放置黑皇后 dfs_black(1); cout << total_ways << endl; return 0; }