POJ-1321-棋盘问题
POJ-1321-棋盘问题
http://poj.org/problem?id=1321
基本的DFS
#include<stdio.h>#include<string.h>#include<stdlib.h>int n,t,ans;char map[10][10];int visit[10];void dfs(int x,int y){int i;if(y==t){ans++;return;}if(x>=n)return; for(i=0;i<n;i++) //x行放棋子{ if(!visit[i]&&map[x][i]=='#'){visit[i]=1;dfs(x+1,y+1);visit[i]=0;}}dfs(x+1,y); //x行不放棋子}int main(){int i;while(scanf("%d%d",&n,&t),n!=-1&&t!=-1){for(i=0;i<n;i++)scanf("%s",map[i]);ans=0;memset(visit,0,sizeof(visit));dfs(0,0);printf("%d\n",ans);}return 0;}