CodeForces King of the Waves(DFS )

题意:已知– ’1’ if person i will win against person j.(1代表i能赢j)
        – ’0’ if person i will lose against person j.(0代表i会输给j)

        – ’X’ if i = j.(X代表平局)。

有n个人(0~n-1),问怎么安排出场顺序能使0赢。

思路:一开始觉得排在前面的一定能被后边的打败,从而忽略了0可以打败多个的事实。用DFS搜索只有部分数据通过。
其实可以将问题简化为如果0能胜利,则剩余的n-1个人要么被0打败,要么被0所打败的人打败这几种情况,也就说在DFS的时候从0开始搜索,能被0打败的放入串中,如果串在等于n之前断了,继续从0的下一条串遍历(0能打败的人不止一个的情况下),只要这n-1个人都能被0或其他0所打败的人打败,被遍历到vis[i]都为1即可(即在DFS回溯的时候之前有对手被打败的就不在恢复为遍历之前的状态)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int Map[1005][1005];///存图
int vis[1005];///标记是否被遍历
int ans[1005];///存出场顺序
int n,cnt,flag;
void DFS(int a)
{
    if(cnt==n)
    {
        flag=1;
        return;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(Map[a][i]==1&&vis[i]==0)
            {
                vis[i]=1;///i能被a打败,则加入串中
                ans[cnt++]=i;///计数增加
                DFS(i);
            }
        }
    }
}
int main()
{
    flag=0;
    scanf("%d%*c",&n);
    char e;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%c",&e);
            if(e=='X')
                Map[i][j]=2;
            else
                Map[i][j]=e-'0';
        }
        getchar();
    }
    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cout<<Map[i][j]<<" ";
        cout<<endl;
    }*/
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    cnt=1;
    DFS(0);
    if(flag==0) printf("impossible\n");
    else
    {
        for(int i=cnt-1;i>=0;i--)
            printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}

版权声明:本文为a17865569022原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/a17865569022/article/details/80169958