POJ 1321 C++ : 棋盘问题

2016-12-30 19:50:43来源:CSDN作者:u010203544人点击

第七城市

思路:

1.DFS逐行的搜索,定义vis数组记录某一列上是否已经有棋子存在,每次行数加1迭代,最后别忘了搜索完一行都没有放棋子的情况2.特别注意:输入的时候用getchar读入一行,然后存入字符数组中
#include <stdio.h>#include <iostream>using namespace std;int n;int k;int ans=0;int vis[9];char a[9][9];int num;void Dfs(int idx){	if(num==k){ans++;return;}	if(idx>n)return;	int i;	for(i=1;i<=n;i++){		if(vis[i]==0&&a[idx][i]=='#'){			vis[i]=1;			num++;			Dfs(idx+1);			vis[i]=0;			num--;		}	}	Dfs(idx+1);}int main(){	while(scanf("%d %d",&n,&k)&&n!=-1&&k!=-1){		num=0;		ans=0;		int i,j;		for(i=1;i<=n;i++)vis[i]=0;		getchar();		for(i=1;i<=n;i++){			for(j=1;j<=n;j++){				scanf("%c",&a[i][j]);			}			getchar();		}		Dfs(1);        cout<<ans<<endl;	}	return 0;}


第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台