Codeforces #139 Snake

問題概要

蛇がN*Mサイズのブロックを動き回る。りんごに辿り着くまでに蛇が移動しなければならない最小移動数を求めよ。

方針

（蛇の頭の座標、蛇の体部の相対座標）を状態数にしてBFSする。この「相対座標を状態数にとる」という発想はおもしろいと思いました。各部位について、相対座標は2bitで表現します。蛇の体部は最大で8つの部位から成り立っているので、全体として2^16あれば頭以外の部分の位置を表現できます。

ソースコード

view plainprint?

1. #define REP(i,n) for(int i=0; i<(int)(n); i++)  
2. #define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)  
3. #define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)    
4.   
5. typedef pair<int, pair<int, int> > pii;  
6.   
7. const int INF = 1<<30;  
8. int r,c;  
9. string bd[16];  
10. int vis[16][16][1<<16];  
11. int dx[] = {-1, 0, 1, 0};  
12. int dy[] = {0, 1, 0, -1};  
13. vector<pii> snake;  
14.   
15. struct status {  
16.     int x;     // x of snake's head  
17.     int y;     // y of snake's head  
18.     int dir;   // directions of snake's body  
19. };  
20.   
21. int getDir(int sx, int sy, int tx, int ty) {  
22.     if (sy == ty) {  
23.         if (sx < tx) return 0;  
24.         return 2;  
25.     }  
26.     else {  
27.         if (sy < ty) return 3;  
28.         return 1;  
29.     }  
30.     return -1;  
31. }  
32.   
33. bool hitBody(int x, int y, int dir) {  
34.     int hx = x;  
35.     int hy = y;  
36.   
37.     int N = snake.size();  
38.     int mask = (N-2)*2;  
39.     FOR (i, 1, N) {  
40.         int d = dir >> mask & 3;  
41.   
42.         if (d == 0) ++x;  
43.         else if (d == 1) --y;  
44.         else if (d == 2) --x;  
45.         else ++y;  
46.                    
47.         if (x == hx && y == hy)  
48.             return true;  
49.   
50.         mask -= 2;  
51.     }  
52.     return false;  
53. }  
54.   
55. int main() {  
56.     cin >> r >> c;  
57.     REP(i, r) cin >> bd[i];  
58.       
59.     REP(i, r) REP(j, c) if ('1' <= bd[i][j] && bd[i][j] <= '9') {  
60.         snake.push_back(make_pair(bd[i][j]-'0', make_pair(i, j)));  
61.     }  
62.   
63.     sort(snake.begin(), snake.end());  
64.     int dir = 0;  
65.     FOR (i, 1, snake.size()) {  
66.         dir <<= 2;  
67.         pair<int, int> p1 = snake[i-1].second;  
68.         pair<int, int> p2 = snake[i].second;  
69.   
70.         dir += getDir(p1.first, p1.second, p2.first, p2.second);  
71.     }  
72.   
73.     int ret = -1;  
74.     queue<status> q;  
75.     pair<int, int> head = snake[0].second;  
76.     q.push((status){head.first, head.second, dir});  
77.     memset(vis, -1, sizeof(vis));  
78.     vis[head.first][head.second][dir] = 0;  
79.   
80.     while (!q.empty()) {  
81.         int x = q.front().x;  
82.         int y = q.front().y;  
83.         int dir = q.front().dir;  
84.           
85.         if (bd[x][y] == '@') {  
86.             ret = vis[x][y][dir];  
87.             break;  
88.         }  
89.   
90.         q.pop();  
91.           
92.         REP(k, 4) {  
93.             int xx = x + dx[k];  
94.             int yy = y + dy[k];  
95.   
96.             if (xx < 0 || xx >= r) continue;  
97.             if (yy < 0 || yy >= c) continue;  
98.             if (bd[xx][yy] == '#') continue;  
99.   
100.             int dir_t = dir >> 2;  
101.             dir_t += getDir(xx, yy, x, y) << 2 * (snake.size()-2);  
102.             if (hitBody(xx, yy, dir_t)) continue;  
103.               
104.             if (vis[xx][yy][dir_t] == -1) {  
105.                 vis[xx][yy][dir_t] = vis[x][y][dir] + 1;  
106.                 q.push((status){xx, yy, dir_t});  
107.             }  
108.         }  
109.     }  
110.   
111.     cout << ret << endl;  
112.   
113.     return 0;  
114. }  

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

typedef pair<int, pair<int, int> > pii;

const int INF = 1<<30;
int r,c;
string bd[16];
int vis[16][16][1<<16];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
vector<pii> snake;

struct status {
    int x;     // x of snake's head
    int y;     // y of snake's head
    int dir;   // directions of snake's body
};

int getDir(int sx, int sy, int tx, int ty) {
    if (sy == ty) {
        if (sx < tx) return 0;
        return 2;
    }
    else {
        if (sy < ty) return 3;
        return 1;
    }
    return -1;
}

bool hitBody(int x, int y, int dir) {
    int hx = x;
    int hy = y;

    int N = snake.size();
    int mask = (N-2)*2;
    FOR (i, 1, N) {
        int d = dir >> mask & 3;

        if (d == 0) ++x;
        else if (d == 1) --y;
        else if (d == 2) --x;
        else ++y;
                 
        if (x == hx && y == hy)
            return true;

        mask -= 2;
    }
    return false;
}

int main() {
    cin >> r >> c;
    REP(i, r) cin >> bd[i];
    
    REP(i, r) REP(j, c) if ('1' <= bd[i][j] && bd[i][j] <= '9') {
        snake.push_back(make_pair(bd[i][j]-'0', make_pair(i, j)));
    }

    sort(snake.begin(), snake.end());
    int dir = 0;
    FOR (i, 1, snake.size()) {
        dir <<= 2;
        pair<int, int> p1 = snake[i-1].second;
        pair<int, int> p2 = snake[i].second;

        dir += getDir(p1.first, p1.second, p2.first, p2.second);
    }

    int ret = -1;
    queue<status> q;
    pair<int, int> head = snake[0].second;
    q.push((status){head.first, head.second, dir});
    memset(vis, -1, sizeof(vis));
    vis[head.first][head.second][dir] = 0;

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        
        if (bd[x][y] == '@') {
            ret = vis[x][y][dir];
            break;
        }

        q.pop();
        
        REP(k, 4) {
            int xx = x + dx[k];
            int yy = y + dy[k];

            if (xx < 0 || xx >= r) continue;
            if (yy < 0 || yy >= c) continue;
            if (bd[xx][yy] == '#') continue;

            int dir_t = dir >> 2;
            dir_t += getDir(xx, yy, x, y) << 2 * (snake.size()-2);
            if (hitBody(xx, yy, dir_t)) continue;
            
            if (vis[xx][yy][dir_t] == -1) {
                vis[xx][yy][dir_t] = vis[x][y][dir] + 1;
                q.push((status){xx, yy, dir_t});
            }
        }
    }

    cout << ret << endl;

    return 0;
}