读题可以知道是DFS，注意一点，题目说的是赢过，所以str[i][j]=‘W',那么g[i][j]=1,str[i][j]='L',g[j][i]=1
然后就常规搜索即可，还有一点就是剪枝，如果没有可以回到0的点，就直接返回。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,g[30][30],tmp[30],flag,vis[30]; 5 char str[30][30]; 6 7 void dfs(int k,int step) { 8 if(flag) return; 9 tmp[step]=k+1; 10 if(step==n-1) { 11 if(g[k][0]) { 12 flag=1; 13 return; 14 } 15 } 16 int i; 17 for(i=1;i<n;i++) { 18 if(vis[i]==0&&g[i][0]) break; 19 } 20 if(i==n) return; 21 for(i=0;i<n;i++) { 22 if(g[k][i]&&vis[i]==0) { 23 vis[i]=1; 24 dfs(i,step+1); 25 vis[i]=0; 26 } 27 } 28 } 29 30 int main() { 31 scanf("%d",&n); 32 for(int i=0;i<n;i++) { 33 scanf("%s",str[i]); 34 for(int j=0;j<n;j++) { 35 if(str[i][j]=='W') g[i][j]=1; 36 else if(str[i][j]=='L') g[j][i]=1; 37 } 38 } 39 vis[0]=1; 40 dfs(0,0); 41 if(flag) { 42 for(int i=0;i<n-1;i++) printf("%d ",tmp[i]); 43 printf("%d",tmp[n-1]); 44 } else puts("No Solution"); 45 }