给你n,代表有0 n-1个人,给你n行,每行n个字符, 字符是X,i=j就是这个人在这个位置 1 代表,i人能赢j人当king 0代表输; 游戏规则是b 是king a能赢b a当king 问裁判按什么安排顺序0能当king
一开始思路是A能打赢B就连A到B，然后看能否从0遍历到最后的n-1。比赛时考虑到数据量是1000，dfs最坏的复杂度是1000！。就放弃了，而我在想着如何剪枝，以失败告终。
其实这题一开始就忽略了题意是说如何安排顺序使得0能最终获胜，而不是前一个人必须被后一个人打败（这个就是我的想法），直到0打败倒数第二个！可以说，我之前那样想的是“如何安排顺序使得0能最终获胜”的特殊情况！找到特殊情况可不容易啊！所以超时是妥妥的……
dfs遍历复杂时，可看看题意是否把握好。比如这题，“如何安排顺序使得0能最终获胜”，加入顺序为k1 k2 k3 k4……k1到k2可不是k1指向k2哦！还可以是k2指向k1.（k2 来挑战k1，只不过失败了而已）
#include <bits/stdc++.h> using namespace std; int n; int a[1010][1010]; int used[1010]; int ans[1010]; char str[1010]; bool f; int t; void dfs(int u) { if(t==n-1) { f=1; return ; } for(int i=0; i<n; i++) if(a[u][i] && !used[i]) { used[i]=1; ans[t++]=i; dfs(i); } return ; } int main() { cin>>n; f=0,t=0; memset(used,0,sizeof used); for(int i=0; i<n; i++) { scanf("%s",str); for(int j=0; j<n; j++) { if(str[j]=='X') a[i][j]=0; else if(str[j]=='1') a[i][j]=1; else a[i][j]=0; } } used[0]=1; dfs(0); if(f) { for(int i=t-1; i>=0; i--) cout<<ans[i]<<' '; cout<<0<<endl; } else cout<<"impossible"<<endl; return 0; }