Gym 100952E E. Arrange Teams dfs、剪枝

Source

UESTC 2016 Summer Training #21

Gym 100952E

My Solution

dfs、剪枝

首先用 pai[][]布尔数组双向的记录 那些 pair

然后void dfs(int k) 表示当前正在处理 队伍 k， 然后遍历 所有 i, j 如果没有访问过， 并且满足条件 则dfs(k + 1)

直到顺利的把所以的t个队伍都填进去了， 那一个分枝才ans++; return;

剪枝以后的复杂度不大算的出来， 嘿嘿， 但看数据大小 (1  ≤  n,m  ≤  11) and (1  ≤  t  ≤  10) 这样做一般可以pass the tests

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 16;

int n, m, t, ans, vis[maxn][maxn];
bool pai[maxn][maxn];


void dfs(int k)
{
    if(k == t + 1) {ans++; return;}

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(vis[i][j]) continue;
            if(!pai[vis[i-1][j]][k] && !pai[vis[i+1][j]][k]
                && !pai[vis[i][j-1]][k] && !pai[vis[i][j+1]][k]){
                    vis[i][j] = k;
                    dfs(k + 1);
                    vis[i][j] = 0;
            }
        }
    }
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL
    int T, q, x, y;
    scanf("%d", &T);
    while(T--){
        ans = 0;
        memset(pai, false, sizeof pai);
        memset(vis, 0, sizeof vis);

        scanf("%d%d%d%d", &n, &m, &t, &q);
        //!前面少打了一个 %d  然后运行了60多秒才输出结果， 关键是有些答案还是正确的， 又是一条智障的经验啊 (┬＿┬)
        for(int i = 0; i < q; i++){
            scanf("%d%d", &x, &y);
            pai[x][y] = true;
            pai[y][x] = true;
        }
        dfs(1);
        if(ans != 0) printf("%dn", ans);
        else printf("impossiblen");
    }
    return 0;
}