文章出處
文章列表
題意： 給定一個n*n（n<=8）的棋盤， 有些地方能放棋子， 有些不能。 放m個棋子， 求能使這m個棋子不同行且不同列的方案數。
分析： 用一個一維數組標記行和列， 深搜一下。
#include<cstdio> #include<cstring> char s[10][10]; int n, m; int vis[10]; int ans; void dfs(int cur, int step) { if(step==m) { ans++; return; } if(cur>n-1) return; for(int i=cur; i<n; i++) for(int j=0; j<n; j++) if(s[i][j]=='#'&&!vis[j]) { vis[j]=1; dfs(i+1, step+1); vis[j]=0; } } int main() { while(scanf("%d%d", &n, &m)) { if(n==-1&&m==-1) break; for(int i=0; i<n; i++) scanf("%s", s[i]); memset(vis, 0, sizeof(vis)); ans = 0; dfs(0, 0); printf("%d\n", ans); } return 0; }
文章列表
全站熱搜
留言列表
