7-15 球队“食物链” (30 分)
#include<bits/stdc++.h> using namespace std; bool vis[40]; bool dp[30][(1 << 20) + 1]; char tu[40][40]; int ans[213]; int n; int dfs(int x,int c,int state){ if(c==n){ if(tu[x][1]=='W'||tu[1][x]=='L')return 1; } for(int i=1;i<=n;i++){ if(!vis[i]&&(tu[x][i]=='W'||tu[i][x]=='L')&&!dp[i][state]){ vis[i] = 1; ans[c] = i; if(dfs(i,c+1,state|(1<<(i-1))))return 1; vis[i] = 0; dp[i][state] = 1; } } return 0; } int main() { cin>>n; for(int i=1;i<=n;i++){ scanf("%s",tu[i]+1); } memset(vis,0,sizeof vis); memset(dp,0,sizeof dp); vis[1] = 1; ans[0] = 1; if(dfs(1,1,1)){ int top = 1; for(int i=0;i<n;i++){ if(top)top =0; else printf(" "); printf("%d",ans[i]); } } else{ printf("No Solution\n"); } return 0; }
CODE2:
//注意:i战胜j可以是st[i][j]='W'||st[j][i]='L'; #include<stdio.h> #include<string.h> int n; char st[25][25]; int a[25]; int ans; int l; int visit[25]; int u; void dfs(int v) { int i,j; if(ans==1) return ; if(l==n) { if(st[v][u]=='W'||st[u][v]=='L') { for(j=0;j<n-1;j++) printf("%d ",a[j]+1); printf("%d\n",a[n-1]+1); ans=1; return ; } } for(i=0;i<n;i++) { if(ans==1) return ; int tag=0; //优化,因为是一个环,若该点没有战胜0,则就没有必要对该点判断下去 for(j=1;j<n;j++) { if(!visit[j]&&st[j][0]=='W'||st[0][j]=='L') { tag=1; break; } } if(tag==0) return ; if(!visit[i]&&(st[v][i]=='W'||st[i][v]=='L')) { visit[i]=1; a[l]=i; l++; dfs(i); visit[i]=0; l--; } } } int main() { int i,j; scanf("%d",&n); for(i=0;i<n;i++) scanf("%s",st[i]); int tag=0; //优化,因为是一个环,所以若存在一个食物链,就直接判断从0开始是否可以即可 for(i=1;i<n;i++) { if(st[i][0]=='W'||st[0][i]=='L') { tag=1; break; } } if(tag==0) { printf("No Solution\n"); return 0; } memset(visit,0,sizeof(visit)); ans=0; l=0; u=0; a[l]=0; l++; visit[0]=1; dfs(0); if(ans==0) printf("No Solution\n"); return 0; }