UVA 1533 Moving Pegs(bfs+hash)

제목:

아이디어:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int dx[] = {-1,-1, 0, 0, 1, 1};
const int dy[] = {-1, 0,-1, 1, 0, 1};
const int N = 1<<16;
struct State {
    int grid[5][5], num; //the last pos and the step
    vector< pair<int,int> > path; //first from second to
    //init
    State() {
        memset(grid, false, sizeof(grid));
        num = 0;
        path.clear();
    }
    //create function
    State(int _grid[][5], int _num) {
        memcpy(grid, _grid, sizeof(grid));
        num = _num;
    }
    //hash
    int Hash() {
        int sum = 0, cnt = 1;
        for(int i = 0; i < 5; i++)
            for(int j = 0; j <= i; j++)
                sum |= grid[i][j] << cnt++;
        return sum;
    }
};
vector< pair<int,int> > ans;
int state[5][5], vis[N];
int empty;

void init() {
    memset(vis, false, sizeof(vis));
    memset(state, -1, sizeof(state));
    int cnt = 1;
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j <= i; j++) {
            if(empty != cnt++) state[i][j] = 1;
            else state[i][j] = 0;
        }
    }
}

int trans(int x, int y) {
    return x*(x+1)/2 + (y+1);
}

bool check(int grid[][5]) {
    int pos = 0;
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j <= i; j++) {
            if(grid[i][j]) pos = trans(i, j);
        }
    }
    return pos == empty;
}

bool overBound(int x, int y) {
    if(x < 0 || x >= 5 || y < 0 || y >= 5)
        return true;
    return false;
}

bool bfs() {
    //init
    queue<State> que;
    que.push(State(state, 14));
    State front = que.front(), tmpState;
    vis[front.Hash()] = true;

    int nx, ny, len;
    while(!que.empty()) {
        front = que.front(); que.pop();
        if(front.num == 1 && check(front.grid)) {
            ans = front.path; return true;
        }
        for(int x = 0; x < 5; x++) {
            for(int y = 0; y <= x; y++) { //num
                if(front.grid[x][y] == 0) continue;
                for(int i = 0; i < 6; i++) { //direction
                    nx = x + dx[i], ny = y + dy[i];
                    if(!overBound(nx, ny)) {
                        len = 1;
                        tmpState = front;
                        while(tmpState.grid[nx][ny] == 1 && !overBound(nx, ny)) {
                            tmpState.grid[nx][ny] = 0;
                            len++;
                            nx += dx[i], ny += dy[i];
                        }
                    }
                    if(tmpState.grid[nx][ny] == -1 || overBound(nx,ny) || len < 2) continue;
                    tmpState.grid[nx][ny] = 1; tmpState.grid[x][y] = 0;
                    tmpState.num -= (len-1);
                    tmpState.path.push_back(make_pair(trans(x,y), trans(nx,ny)));
                    int tmp = tmpState.Hash();
                    if(!vis[tmp]) {
                        vis[tmp] = true;
                        que.push(tmpState);
                    }
                }
            }
        }
    }
    return false;
}

int main() {
// freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &empty);
        init();
        if(!bfs()) {
            printf("IMPOSSIBLE
");
        }else {
            printf("%d
", ans.size());
            printf("%d %d", ans[0].first, ans[0].second);
            for(int i = 1; i < ans.size(); i++)
                printf(" %d %d", ans[i].first, ans[i].second);
            puts("");
        }
    }
    return 0;
}