POJ 1321 棋盘问题[DFS]

#include <cstdio>
using namespace std;

#define sf scanf
#define pf printf
#define rep(i,a,b) for(int i=a;i<(b);++i)

char G[10][10];
bool fg[10] = {0};  // 走过为真
int ans = 0, n, k;

void dfs(int cur, int x) {  // cur为已摆的棋子数， x 为行数
    if(cur == k) {
        ans++;
        return;
    }
    rep(i, x, n)
        rep(j, 0, n)
            if(G[i][j] == '#' && !fg[j]) {
                fg[j] = true;
                dfs(cur+1, i+1);  // 下一行继续摆下一个棋子
                fg[j] = false;
            }
}

int main() {
    while(sf("%d%d", &n, &k) == 2 && n != -1 && k != -1) {
        rep(i,0,n) sf("%s",G[i]);
        dfs(0, 0);  // 第一行开始摆
        pf("%d\n", ans); ans = 0;
    }
    return 0;
}