L3-015 球队“食物链”(深搜+剪枝)

输入样例1：
5
-LWDW
W-LDW
WW-LW
DWW-W
DDLW-

输出样例1：
1 3 5 4 2

输入样例2：
5
-WDDW
D-DWL
DD-DW
DDW-D
DDDD-

输出样例2：
No Solution

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=20+5,INF=0x3f3f3f3f;
int fin[N],e[N][N],use[N];
int tot,n;
vector<int>vec[N];
int dfs(int pos,int x)
{
    // 也不需要fin[n+1]=-1的话 return 1,因为直接就在下面的for里面层层瞬间返回了
    if(pos==n)
    {
        if(!e[x][1])
            return 0;
        fin[pos+1]=-1;
        return 1;
    }
    int i;
    for(i=1;i<=n;i++)//若剩下的找不到胜过i的,则剪枝
    {
        if(!use[i])
        {
            if(e[i][1])
                break;
        }
    }
    if(i==n+1)
        return 0;
    vector<int>::iterator it;
    for(it=vec[x].begin();it!=vec[x].end();it++)
    {
        int y=*it;
        if(use[y])
            continue;
        use[y]=1;
        if(dfs(pos+1,y))
        {
            //use[y]=0;(没必要 既然在前面限定的条件下 pos+1可以放y,早就说明victory了,直接返回就OK)
            fin[pos+1]=y;
            return 1;
        }
        use[y]=0;
    }
    return 0;
}
char str[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=n;j++)
        {
            if(str[j]=='W')
                vec[i].push_back(j),e[i][j]=1;
            if(str[j]=='L')
                vec[j].push_back(i),e[j][i]=1;
        }
    }
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        if(vec[i].empty())
        {
            flag=1;
            break;
        }
        sort(vec[i].begin(),vec[i].end());
    }
    if(flag)
        puts("No Solution");
    else
    {
        use[1]=1,fin[1]=1;
        dfs(1,1);
        if(fin[n+1]!=-1)
            puts("No Solution");
        else
        {
            for(int i=1;i<=n;i++)
                printf("%d%c",fin[i],(i==n)?'\n':' ');
        }
    }
}