#DP #LiveArchive #Masks #TLE #UnSolved

3276 - The Great Wall Game - TLE.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int OO = 1e4;

int getBit(int num, int indx) {
    return ((num>>indx) & 1) == 1;
}

int setBit1(int num, int indx) {
    return num | (1<<indx);
}

int setBit0(int num, int indx) {
    return num & ~(1<<indx);
}

int cntBits(int num) {
    int ret = 0;
    while(num) {
        if(num%2) {
            ret++;

        }
        num/=2;
    }
    return ret;
}

int n;
vector<int> matrix;
//map<vector<int>, int> cache;
int di[] = {-1, +1, +0, +0};
int dj[] = {+0, +0, -1, +1};

bool isSolution(vector<int> masks) {
    bool isGood = true;
    lp(i, n) {
        isGood = true;
        lp(j, n) {
            if(getBit(masks[i], j) != 1) {
                isGood = false;
                break;
            }
        }
        if(isGood) { //cout << "ROW" << endl;
        return 1; }
    }

    lp(j, n) {
        isGood = true;
        lp(i, n) {
            //cout << i <<  "  " << j << endl;
            if(getBit(masks[i], j) != 1) {

                isGood = false;
                break;
            }
        }
        if(isGood) { //cout << "COL" << endl;
                return 1; }
    }
    isGood = true;
    lp(i, n) {
        if(getBit(masks[i], i) != 1) {
            isGood = false;
            break;
        }
    }
    if(isGood) {//cout << "DIAG 1" << endl;
            return 1;}
    isGood = true;
    bool isGood2 = true;
    for(int i = n-1; i>=0;i--) {
        isGood &= getBit(masks[i], i);
        isGood2 &= getBit(masks[i], n-i-1);
    }
    return isGood || isGood2;
}
/*

void printSolution(vector<int> masks) {
    lp(i, n) {
        lp(j, n) {
            cout << getBit(masks[i], j);
        }
        cout << endl;
    }
}


int minWall(vector<int> masks) {
    if(cache.find(masks) != cache.end())
        return cache[masks];
    int &ret = cache[masks];
    if(isSolution(masks)) {
        //printSolution(masks);
        //getchar();
        return ret = 0;
    }



    ret = OO;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
            if(getBit(masks[i], j)) {
                for(int k = 0 ; k < 4 ; k++) {
                    int x1 = i + di[k];
                    int y1 = j + dj[k];
                    if(x1 >= 0 && x1 < n && y1 >= 0 && y1 < n && getBit(masks[x1], y1) == 0) {
                        //cout << "-----------\n";
                        //printSolution(masks);
                        vector<int> tmpmasks = masks;
                        tmpmasks[x1] = setBit1(tmpmasks[x1], y1);
                        tmpmasks[i] = setBit0(tmpmasks[i], j);
                        //cout << "-----------\n";
                        //printSolution(tmpmasks);
                        //getchar();
                        ret = min(ret, 1+minWall(tmpmasks));
                    }
                }
            }
        }
    }

    return ret;
}
*/
int main() {
    int t = 0;
    int x, y;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    scanf("%d", &n);
    while(n!=0) {
        if(t!=0) printf("\n");
        //cache.clear();
        matrix.clear();
        lp(i, n) matrix.push_back(0);
        lp(i, n) {
            scanf("%d%d", &x, &y);
            matrix[x-1] = setBit1(matrix[x-1], y-1);
        }

        queue<pair<vector<int>, int>> q;
        q.push(make_pair(matrix, 0));
        set<vector<int>> cache;
        int answer = -1;
        while(q.size()) {
            vector<int> tmp = q.front().first;
            int tmpu = q.front().second;
            q.pop();

            if(cache.count(tmp)) {
                continue;
            }
            cache.insert(tmp);
            if(isSolution(tmp)) {
                answer = tmpu;
                break;
            }

            for(int i = 0 ; i < n ; i++) {
                for(int j = 0 ; j < n ; j++) {
                    if(getBit(tmp[i], j)) {
                        for(int k = 0 ; k < 4 ; k++) {
                            int x1 = i + di[k];
                            int y1 = j + dj[k];
                            if(x1 >= 0 && x1 < n && y1 >= 0 && y1 < n && getBit(tmp[x1], y1) == 0) {
                                vector<int> tmpmasks = tmp;
                                tmpmasks[x1] = setBit1(tmpmasks[x1], y1);
                                tmpmasks[i] = setBit0(tmpmasks[i], j);
                                if(cache.count(tmpmasks) == 0)
                                    q.push(make_pair(tmpmasks, tmpu+1));
                            }
                        }
                    }
                }
            }

        }

        printf("Board %d: %d moves required.\n", t+1, answer);
        t++;
        scanf("%d", &n);
    }
    /*
    cin>>n;
    int x, y;
    lp(i, 16) matrix.push_back(0);
    lp(i, n) {
        cin>>x>>y;
        matrix[x-1] = setBit1(matrix[x-1], y-1);
    }
    printSolution(matrix);
    if(isSolution(matrix)) {
        cout << "Ok!" << endl;
    } else {
        cout << "Not!" << endl;
    }*/
    return 0;
}