Algoogle

Algorithm for Programming Contest

ACM-ICPC Tokyo Regional 2014 E Automotive Navigation

Category: ICPC Tag: implementation

Automotive Navigation

問題概要


x軸, y軸に平行な線分で繋がれたコースがある.
今, 車のGPSが位置(x0, y0)で壊れた.
以降単位時間毎にに前回の観測から移動した距離と現在の向いている向きを観測し報告する.
向きは曲がり角にいる場合は曲る前と曲がった後のいずれかである.
また車はUターンできない.
時間tが経過したとき, 車の存在する場所としてありえる場所を列挙しろ.

解法


問題の時間をターンということにする.
各座標について上下左右に移動可能かを入力からつくる.
あとは毎ターン距離dを移動させるのをBFSする.
状態が増えすぎるとあれなので,(位置, 向き, そのターンでの移動距離)で既にチェック済みか記録しておく.
次のターンの開始状態としてあり得るものを候補に列挙していく.
向きが移動したあとというのは次のターンで移動距離1の状態ということでつくる.
答えにするときは戻せばよい.

コード


(E.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
#include <bits/stdc++.h>
using namespace std;

struct point
{
        int x, y, dir, dist;
        bool operator<(const point &p) const { return x!=p.x? x < p.x: y < p.y;}
        bool operator==(const point &p) const { return x == p.x and y == p.y;}
};

const int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};
int n, t, sx, sy, f[64][64][4];
int d[128], p[128], done[64][64][4][16];
vector<point> cand, ans;

void simulate(int dist, int edir)
{
        queue<point> q;
        for(auto &e: cand) if(!e.dist) q.push(e);
        for(auto &e: cand) if(e.dist) q.push(e);
        cand.clear();
        memset(done,0,sizeof(done));
        while(!q.empty()) {
                point v = q.front(); q.pop();
                if(done[v.x][v.y][v.dir][v.dist]) continue;
                done[v.x][v.y][v.dir][v.dist] = 1;
                if(v.dist == dist and v.dir == edir) cand.push_back((point){v.x,v.y,edir,0});
                for (int i = 0; i < 4; i++) {
                        if((v.dir+2)%4 == i or !f[v.x][v.y][i]) continue;
                        int nx = v.x+dx[i], ny = v.y+dy[i];
                        if(v.dist == dist) {
                                if(i == edir) cand.push_back((point){nx,ny,edir,1});
                                else continue;
                        }
                        q.push((point){nx,ny,i,v.dist+1});
                }
        }
}

void solve()
{
        cand.push_back((point){sx,sy,0,0});
        cand.push_back((point){sx,sy,2,0});
        for (int i = 0; i < t; i++) simulate(d[i], p[i]);
        for(auto &e: cand) {
                if(e.dist) ans.push_back((point){e.x-dx[e.dir],e.y-dy[e.dir],e.dir,0});
                else ans.push_back(e);
        }
        sort(begin(ans),end(ans));
        ans.erase(unique(begin(ans),end(ans)),end(ans));
        for(auto &e: ans) cout << e.x << " " << e.y << endl;
}

void input()
{
        cin >> n >> sx >> sy >> t;
        int x1, y1, x2, y2;
        for (int i = 0; i < n; i++) {
                cin >> x1 >> y1 >> x2 >> y2;
                if(x1 == x2) for (int y = min(y1,y2); y < max(y1,y2); y++) f[x1][y][0] = f[x1][y+1][2] = 1;
                else for (int x = min(x1,x2); x < max(x1,x2); x++) f[x][y1][1] = f[x+1][y1][3] = 1;
        }
        const string dir = "NESW";
        char c;
        for (int i = 0; i < t; i++) {
                cin >> d[i] >> c;
                p[i] = dir.find(c);
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments