PAT-天梯赛习题集-L3-015-球队“食物链”

描述

题解

一个常规的 dfs 问题，十分容易想到思路，但是需要注意的是这里有一个剪枝——如果当前所剩的节点里没有一个能回到起点，那么就返回，这个剪枝至关重要，不然会在第四组数据超时，丢掉 8 分，想想就肉疼啊，一开始我也没有想到这个，以为是 OJ 测评信息太假了，仔细想了想，才发现还可以这么剪枝，GG~~~

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 25;

char achi[MAXN][MAXN];

int N;
int flag = 1;
int L[MAXN];
bool vis[MAXN];

void dfs(int n, int last)
{
    if (n > N)
    {
        if (achi[L[N]][L[1]] == 'W' || achi[L[1]][L[N]] == 'L')
        {
            flag = 0;
        }
        return ;
    }

    int tag = 1;
    for (int i = 1; i <= N; i++)
    {
        if (!vis[i] && (achi[i][L[1]] == 'W' || achi[L[1]][i] == 'L'))
        {
            tag = 0;
            break;
        }
    }
    if (tag)
    {
        return ;
    }

    for (int i = 1; i <= N && flag; i++)
    {
        if (!vis[i] && flag && (achi[last][i] == 'W' || achi[i][last] == 'L'))
        {
            vis[i] = 1;
            L[n] = i;
            dfs(n + 1, i);
            vis[i] = 0;
        }
    }
}

int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        scanf("%s", achi[i] + 1);
    }

    for (int i = 1; i <= N && flag; i++)
    {
        vis[i] = 1;
        L[1] = i;
        dfs(2, i);
        vis[i] = 0;
    }

    if (flag)
    {
        cout << "No Solution\n";
    }
    else
    {
        printf("%d", L[1]);
        for (int i = 2; i <= N; i++)
        {
            printf(" %d", L[i]);
        }
        puts("");
    }

    return 0;
}