【題解】POJ 1321 棋盘问题

#include <iostream>
#include <cstring>
using namespace std;

char a[10][10];
int n, k;
int cnt, ans;
int pos[10];//第i顆棋子擺放在哪一個col

void dfs(int r){
    if (cnt == k){
        ans++;
        return;
    }
    
    if (r >= n) return;
    
    //考慮在row-r放置棋子的可能
    for (int c=0; c<n; c++){
        if (a[r][ c] == '#'){
            bool flag = true;
            for (int i=0; i<cnt; i++){
                //檢查目前已經放置的所有棋子
                if (pos[i] == c){
                    //第i顆棋子已經擺放在col-c
                    flag = false;
                    break;
                }
            }
            if (flag){
                pos[cnt++] = c;
                dfs(r + 1);
                cnt--;
            }
        }
    }
    
    //不在row-r放置棋子，直接跳到下一個row
    dfs(r + 1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> k){
        if (n == -1 && k == -1) break;
        
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                cin >> a[i][j];
            }
        }
        ans = 0; //可行的擺放方案
        cnt = 0; //已經擺放的棋子数目
        memset(pos, -1, sizeof(pos));
        dfs(0);
        cout << ans << '\n';
    }
    
    return 0;
}