Algoogle

Algorithm for Programming Contest

AOJ 1260 Organize Your Train

Category: AOJ Tag: bidirectional-search

Organize Your Train

問題概要


x(<=4)本の列車止める場所があって, それら場所はy本の辺で繋がれている.
右と左で区別する.
列車(最大10両分)があるときそれらを区切って辺にそって移動させる.
辺にそって行くので出た方向と同じ方向から入ってくるときは列車の位置は反転する.
初期状態を終了状態が与えられるので, 最小で何回の移動で初期状態から終了状態にもっていけるか.
移動は最大でも6回である.

解法


初期状態と終了状態の両方から全探索する.
それぞれ3回の移動までやれば両側から探索しているので解がみつかる.
全探索する場合探索が深くなればなるほど状態が多くなるが, このように目的状態が分かっている場合, 両側から半分ずつ調べれば無駄な探索を大幅に省ける.

コード


(1260.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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>

using namespace std;

typedef pair<int,int> pii;
typedef pair<vector<string>,pii> pvspii;

const string dir = "WE";

int N, M;
vector<pii> edge[4][2];
vector<string> lines[2];
map<vector<string>, int> dist[2];

void init(){
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 2; j++)
            edge[i][j].clear();
    for(int i = 0; i < 2; i++){
        lines[i].clear();
        dist[i].clear();
    }

}

bool input(){
    cin >> N >> M;
    if(!N) return 0;
    init();
    for(int i = 0; i < M; i++){
        int a, c;
        char b, d;
        cin >> a >> b >> c >> d;
        int bb = dir.find(b);
        int dd = dir.find(d);
        edge[a][bb].push_back(pii(c,dd));
        edge[c][dd].push_back(pii(a,bb));
    }
    for(int j = 0; j < 2; j++)
        for(int i = 0; i < N; i++){
            string str; cin >> str;
            if(str == "-") lines[j].push_back("");
            else lines[j].push_back(str);
        }
    return 1;
}

int solve(){
    queue<pvspii> que;
    que.push(pvspii(lines[0],pii(0,0)));
    que.push(pvspii(lines[1],pii(0,1)));
    dist[0][lines[0]] = 0;
    dist[1][lines[1]] = 0;
    while(!que.empty()){
        vector<string> line = que.front().first;
        int d = que.front().second.first;
        int s = que.front().second.second;
        int ns = (s + 1) % 2;
        que.pop();
        if(dist[ns].count(line) > 0) return d + dist[ns][line];
        if(d == 3) continue;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < line[i].size(); j++){
                string l = line[i].substr(0,j), r = line[i].substr(j);
                if(l.size() > 0){
                    for(int k = 0; k < edge[i][0].size(); k++){
                        vector<string> next = line;
                        next[i] = r;
                        int ndir = edge[i][0][k].second;
                        int nl = edge[i][0][k].first;
                        if(ndir == 1) next[nl] += l;
                        else{
                            string tl = l;
                            reverse(tl.begin(), tl.end());
                            next[nl] = tl + next[nl];
                        }
                        if(dist[s].count(next) == 0) {
                            que.push(pvspii(next,pii(d+1,s)));
                            dist[s][next] = d+1;
                        }
                    }
                }
                if(r.size() > 0){
                    for(int k = 0; k < edge[i][1].size(); k++){
                        vector<string> next = line;
                        next[i] = l;
                        int ndir = edge[i][1][k].second;
                        int nl = edge[i][1][k].first;
                        if(ndir == 0) next[nl] = r + next[nl];
                        else{
                            string tr = r;
                            reverse(tr.begin(), tr.end());
                            next[nl] += tr;
                        }
                        if(dist[s].count(next) == 0){
                            que.push(pvspii(next,pii(d+1,s)));
                            dist[s][next] = d+1;
                        }
                    }
                }
            }
        }
    }
}

int main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments