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; }