Algoogle

Algorithm for Programming Contest

AOJ 2178 Futon

Category: AOJ Tag: bfs

Futon

問題概要


解法


mapで布団の情報を持っておく.
ある布団について頭と足の位置を決めたら
それに隣接する布団の頭と足の位置は決まるのでBFSで決定していく.
そのなかで配置が不可能だったらNoになる.
必ずしもすべてが繋がっているわけではないので,
島になるものをすべてチェックする(BFSが終わった時に未チェックがあれば繰り返す).

コード


(2178.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define fst first
#define snd second
using namespace std;
typedef pair<int,int> pii;
int n;
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};

struct S{
    int x, y, id, head;
    S(int x, int y, int id, int head):x(x),y(y),id(id),head(head){}
};

int main(){
    while(cin>>n,n){
        map<pii, int> id;
        map<pii, int> futon;
        set<pii> notused;
        int x, y;
        char dir;
        rep(i,n){
            cin >> x >> y >> dir;
            notused.insert(pii(x,y));
            id[pii(x,y)] = i;
            futon[pii(x,y)] = -1;
            int d = 3;
            if(dir == 'x') d = 2;
            x += dx[d];
            y += dy[d];
            notused.insert(pii(x,y));
            id[pii(x,y)] = i;
            futon[pii(x,y)] = -1;
        }
        bool ok = true;
        while(!notused.empty()){
            queue<S> que;
            pii p = *notused.begin();
            que.push(S(p.fst,p.snd,id[p],0));
            while(!que.empty()){
                S s = que.front();
                que.pop();
                rep(i,4){
                    int nx = s.x + dx[i], ny = s.y + dy[i];
                    pii np = pii(nx,ny);
                    if(futon.find(np) != futon.end()){
                        if(futon[np] != -1){
                            if(s.id == id[np]){
                                if(futon[np] == s.head){
                                    ok = false;
                                    break;
                                }
                                continue;
                            }
                            if(futon[np] != s.head){
                                ok = false;
                                break;
                            }
                            continue;
                        }
                        else{
                            if(s.id == id[np]) {
                                futon[np] = (s.head + 1) % 2;
                                que.push(S(nx, ny, s.id, futon[np]));
                                notused.erase(notused.find(np));
                                continue;
                            }
                            futon[np] = s.head;
                            que.push(S(nx, ny, id[np], s.head));
                            notused.erase(notused.find(np));
                            continue;
                        }
                    }
                }
                if(!ok) break;
            }
            if(!ok) break;
        }
        cout << (ok? "Yes": "No") << endl;
    }
    return 0;
}

Comments