首页 > 代码库 > POJ 1321 dfs
POJ 1321 dfs
在棋盘上放置棋子使它们任意两个都不在同一行或同一列
dfs(x,k)表示的是访问到第x行已放置了k个棋子
这道题我们以每行或者每列为单位来看题,每次搜索都对一整行进行访问,并在安置棋子的点的列位置上使其visit[col]=1
如果放置成功那么dfs(x+1,k+1),再进行回溯
不论是否成功,都要dfs(x+1,k),确保这个位置我不放棋子也曾进行访问过
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 int mat[9][9],dp[9][9],visit[9],n,k,cnt; 6 7 int dfs(int x,int a) 8 { 9 //if(dp[x][a]) return dp[x][a];这句话写了就错了10 if(a==k) return 1;11 if(x>n) return 0;12 13 int nowstate=0;14 15 for(int i=1;i<=n;i++){16 if(mat[x][i]&&!visit[i]){17 visit[i]=1;18 nowstate+=dfs(x+1,a+1);19 visit[i]=0;20 }21 }22 23 nowstate+=dfs(x+1,a);24 dp[x][a]=nowstate;25 return nowstate;26 }27 int main()28 {29 char a;30 while(scanf("%d%d",&n,&k)){31 32 memset(visit,0,sizeof(visit));33 memset(dp,0,sizeof(dp));34 cnt=0;35 36 if(n==-1&&k==-1)37 break;38 for(int i=1;i<=n;i++)39 for(int j=1;j<=n;j++){40 cin>>a;41 mat[i][j]=a==‘#‘?1:0;42 }43 44 int ans=dfs(1,0);45 printf("%d\n",ans);46 }47 return 0;48 }
POJ 1321 dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。