首页 > 代码库 > POJ 1321 dfs

POJ 1321 dfs

2024-07-21 17:44:26   221人阅读

在棋盘上放置棋子使它们任意两个都不在同一行或同一列

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


联系
我们