poj 1321 棋盤問題 dfs

poj 1321 棋盤問題 dfs

這道題並不是很難，但由於慣性思維，會考慮dirx[]、diry[]進行位置的點變換，但發現這樣子並不很容易就能遞歸出來。
這一題用的行列變換，這道題的價值就在於開拓思維，並不在於難度。

#include
#include
#include
using namespace std;

const int maxn = 10;

char maps[maxn][maxn];
int vis[maxn];
int n, k;
int ans;

void dfs(int x, int cnt){   //x 遍歷行，cnt棋子個數
    if(cnt == k) {
            //printf(#1 );
          ans++; return ;
    }
    if(x > n)   return ;     //2個if順序不能交換 ,對應dfs(x+1, cnt)

    for(int i = 1; i <= n; i++){              //列變換
        if(maps[x][i] =='#' && !vis[i]){
          //  printf(#3 );
            vis[i] = 1;
            dfs(x+1,cnt+1);
            vis[i] = 0;
            //printf(#4 );
        }
    }
   // printf(#2 );
    dfs(x+1, cnt);  //就是說 如果有4個地方可以放旗子，但只有2個棋子，就需要這一步，同時對應第二個if
                    //可以做個實驗把注釋掉的全部取消注釋，並把if交換順序，試一下就知道了
    return;
}

int main(){
    while(scanf(%d%d, &n, &k) != EOF){
        if(n==-1&&k==-1) break;
        ans = 0;
        int cnt1 = 0;
        for(int i = 1; i <= n; i++){
            scanf(%s, &maps[i][1]);
            for(int j = 1; j <= n; j++){
                if(maps[i][j] == '#')
                    cnt1++;
            }
        }
        memset(vis, 0, sizeof(vis));
        if(cnt1==k){
            printf(1
);
        }
        else {
          dfs(1,0);
          printf(%d
, ans);
        }
    }
    return 0;
}