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