L3-015. 球队“食物链”

L3-015. 球队“食物链”

除了一个剪枝，其他一切的都是dfs的常规操作

#include<bits/stdc++.h>

using namespace std;
const int maxn = 30;
char ar[maxn][maxn];
int N;
int  w[maxn][maxn];
bool vis[maxn];
int  ans[maxn];
bool dfs(int i,int num)
{
    if(num == N && w[i][0])
    {
        for(int k = 0; k < N; ++k)
        {
            if(k)
                cout<<' ';
            cout<<ans[k]+1;
        }
        return true;
    }


// 遍历，如果不能和0 形成环，就停止搜索
    int k;
    for( k = 1;k < N; ++k)
    {
        if(!vis[k] && w[k][0])
            break;
    }
    if(k >= N)
        return false;



    for(int j = 1; j < N; ++j)
    {
        if(!vis[j]&&w[i][j])
        {
            ans[num] = j;
            vis[j] = 1;
            if(dfs(j,num+1))
                return true;
            vis[j] = false;
        }
    }
    return false;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin>>N;
    for(int i = 0; i < N; ++i)
        cin>>ar[i];
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            if(i == j)
                continue;
            if(ar[i][j] =='W')
                w[i][j] = 1;
            else if(ar[i][j] == 'L')
                w[j][i] = 1;
        }
    }
    vis[0] = 1;
    ans[0] = 0;
    if(!dfs(0,1))
        printf("No Solution");
    return  0;
}