1266: 棋盘问题

http://tjuacm.chaosheng.top/problem.php?id=1266

方法一：参考 https://lunatic.blog.csdn.net/article/details/98874654 AC
但是不理解为什么for循环后面还要dfs

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

int n, k, cnt, ans;
char matrix[N][N];
bool visit[N];

void dfs(int x){
    if(x == n + 1){
        return;
    }
    for(int i = 1; i <= n; i++){
        if(matrix[x][i-1] == '#' && !visit[i]){
            visit[i] = true;
            cnt++;
            if(cnt == k) ans++;
            dfs(x + 1);
            visit[i] = false;
            cnt--;
        }
    }
    dfs(x+1);
} 

int main(){
    while(cin >> n >> k){
        if(n == -1 && k == -1) break;
        ans = 0;
        cnt = 0;
        memset(visit, false, sizeof(visit));
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < n; j++){
                cin >> matrix[i][j];
            }
        }
        dfs(1);
        printf("%d\n", ans);    
    }
    return 0;
}

方法二：
参考 https://lixiang.blog.csdn.net/article/details/103057068
和我自己想的比较像，但是for循环也有个dfs，再仔细看一下。这里是不选这个点

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

int n, k, ans;
char matrix[N][N];
bool visit[N];

void dfs(int x, int cnt){
    if(cnt == k){
        ans++;
        return;
    }
    if(x >= n){
        return ;
    }

    for(int i = 0; i < n; i++){
        if(matrix[x][i] == '#' && !visit[i]){
            visit[i] = true;
            dfs(x + 1, cnt + 1);
            visit[i] = false;
        }
    }
    dfs(x + 1, cnt);
    return;
} 

int main(){
    while(cin >> n >> k){
        if(n == -1 && k == -1) break;
        ans = 0;
        memset(visit, false, sizeof(visit));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> matrix[i][j];
            }
        }
        dfs(0, 0);
        printf("%d\n", ans);    
    }
    return 0;
}

第一反应这么写，但是会多很多多余的情况。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

int n, k, ans;
char matrix[N][N];
bool row[N];
bool col[N];

void dfs(int c){
    if(c == k){
        ans++;
        return;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(matrix[i][j] == '#' && !row[i] && !col[j]){
                row[i] = 1;
                col[j] = 1;
                //printf("c = %d i = %d j = %d ans = %d\n", c, i, j, ans);
                dfs(c + 1);
                row[i] = 0;
                col[j] = 0;
            }
        }
    }
} 

int main(){
    while(cin >> n >> k){
        if(n == -1 && k == -1) break;
        ans = 0;
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> matrix[i][j];
            }
        }
        dfs(0);
        printf("%d\n", ans);    
    }
    return 0;
}