King of the Waves

题意：

给你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;  
}  

最后

以上就是辛勤柜子为你收集整理的King of the Waves的全部内容，希望文章能够帮你解决King of the Waves所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。