K King of the Waves(不回溯的特殊dfs)

57 阅读 0 评论 38 点赞

我是靠谱客的博主美满百褶裙，最近开发中收集的这篇文章主要介绍K King of the Waves(不回溯的特殊dfs)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

首先分析可知，0应当作为序列尾，而前面放一个0能赢的，同理要保证倒数第二个是
前面序列的最后赢家，要使得前面放一个他能赢的，由此可以写出一个由0开始的
dfs，并在dfs中回溯，如果不成立，再从该位置找到另一个满足条件的点继续dfs

但是这种方法太过费时，而题目中有个关键点，该题只需要最后0能赢，前面的过程
不用严格组成输赢链，假设0的那行为X110000，对于第一个1向下dfs，形成了序列
A(且A序列不完整，不能作为答案)，按第一种写法需要重新从第二个1dfs，但是如
果直接把第二个1放在A序列后，由于A序列最后的赢家会是第一个1，而这两个1，不
论他们两者谁能赢，最后的0都能赢过这两者的胜者，同理每次dfs都可以按这个思路
进行，这样每次dfs都会作为结果的一部分，不用回溯，大大节省时间。

#include <bits/stdc++.h>
using namespace std;
int n;
char wl[1010][1010];
int vis[1010];
int tr[1010];
int flag = 0;
int num=0;
void dfs(int s)
{
    if (num == n - 1)
    {
        flag = 1;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (wl[s][i] == '1' && !vis[i])
        {
            vis[i] = 1;
            tr[num++] = i;
            dfs(i);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    memset(wl, 0, sizeof(wl));
    memset(vis, 0, sizeof(vis));
    memset(tr, 0, sizeof(tr));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> wl[i][j];
        }
    }
    vis[0]=1;
    dfs(0);
    if (flag)
    {
        for (int i = n - 2; i >= 0; i--)
            cout << tr[i] << ' ';
        cout << 0 << endl;
    }
    else
        cout << "impossible" << endl;
        system("pause");
    return 0;
}