Organize Your Train
2007.08.24 22:24 ACM/ICPC 2005
[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem D
[解説]
両側幅優先探索。
詳細は後日書きたいと思います。
[サンプルプログラム]
[解説]
両側幅優先探索。
詳細は後日書きたいと思います。
[サンプルプログラム]
001 #include<iostream>
002 #include<string>
003 #include<queue>
004 #include<map>
005 #define MAX 4
006 #define LIMIT 6
007 #define FORWARD 0
008 #define BACK 1
009 #define WEST 0
010 #define EAST 1
011 #define BUFFER 40
012
013 using namespace std;
014
015 class Load{
016 public:
017 char buffer[BUFFER];
018 int head, tail, size;
019 Load(){}
020 Load( string str ){
021 head = tail = BUFFER/2;
022 size = 0;
023 for ( int i = 0; i < str.size(); i++ ){
024 buffer[tail++] = str[i];
025 size++;
026 }
027 }
028
029 void intoW( char ch ){ buffer[--head] = ch; size++; }
030 void intoE( char ch ){ buffer[tail++] = ch; size++; }
031 char fromW(){ char ch = buffer[head]; head++; size--; return ch; }
032 char fromE(){ char ch = buffer[tail-1]; tail--; size--; return ch; }
033
034 bool operator < ( const Load &l ) const {
035 if ( size != l.size ) return size < l.size;
036 for ( int i = head, j = l.head; i < tail; i++, j++ ){
037 if ( buffer[i] == l.buffer[j] ) continue;
038 return buffer[i] < l.buffer[j];
039 }
040 return false;
041 }
042
043 bool operator == ( const Load &l ) const {
044 if ( size != l.size ) return false;
045 for ( int i = head, j = l.head; i < tail; i++, j++ ){
046 if ( buffer[i] != l.buffer[j] ) return false;
047 }
048 return true;
049 }
050
051 bool operator != ( const Load &l ) const {
052 if ( size != l.size ) return true;
053 for ( int i = head, j = l.head; i < tail; i++, j++ ){
054 if ( buffer[i] != l.buffer[j] ) return true;
055 }
056 return false;
057 }
058 };
059
060 class Station{
061 public:
062 int nload;
063 Load loads[MAX];
064 int id;
065
066 Station(){}
067 Station( int nload): nload(nload){}
068
069 bool operator < ( const Station &s ) const {
070 for ( int i = 0; i < nload; i++ ){
071 if ( loads[i] == s.loads[i] ) continue;
072 return loads[i] < s.loads[i];
073 }
074 return false;
075 }
076
077 bool operator == ( const Station &s ) const {
078 for ( int i = 0; i < nload; i++ ){
079 if ( loads[i] != s.loads[i] ) return false;
080 }
081 return true;
082 }
083 };
084
085
086 Station initial, goal;
087 int nload;
088 bool M[MAX][2][MAX][2];
089
090 map<Station, int> BS;
091 map<Station, int> FS;
092
093 Station getNext(Station v, int d, int s, int sd, int t, int td){
094 int nd;
095
096 if ( sd == WEST ){
097 if ( td == WEST ){
098 for ( int i = 0; i < d; i++ ){
099 v.loads[t].intoW(v.loads[s].fromW());
100 }
101 } else {
102 for ( int i = 0; i < d; i++ ){
103 v.loads[t].intoE(v.loads[s].fromW());
104 }
105 }
106 } else {
107 if ( td == WEST ){
108 nd = v.loads[s].size - d;
109 for ( int i = 0; i < nd; i++ ){
110 v.loads[t].intoW(v.loads[s].fromE());
111 }
112 } else {
113 nd = v.loads[s].size - d;
114 for ( int i = 0; i < nd; i++ ){
115 v.loads[t].intoE(v.loads[s].fromE());
116 }
117 }
118 }
119
120 return v;
121 }
122
123 int bfs( Station source, map<Station, int> &D, int mode ){
124 queue<Station> Q;
125 Q.push(source);
126 D[source] = 0;
127
128 Station u, v;
129
130 if ( mode == FORWARD && BS.find(source) != BS.end() ) return BS[source];
131
132 while(!Q.empty()){
133 u = Q.front(); Q.pop();
134 int dist = D[u];
135
136 if ( mode == BACK && dist >= 3 ) return 0;
137
138 for ( int s = 0; s < nload; s++ ){
139 for ( int d = 0; d < u.loads[s].size; d++ ){
140 for ( int t = 0; t < nload; t++ ){
141 for ( int sd = 0; sd < 2; sd++ ){
142 for ( int td = 0; td < 2; td++ ){
143 if ( M[s][sd][t][td] ){
144 v = getNext(u, d, s, sd, t, td );
145 if ( D.find(v) == D.end() ){
146 D[v] = dist + 1;
147 if ( mode == FORWARD ){
148 if ( BS.find(v) != BS.end() ) {
149 return BS[v] + dist + 1;
150 }
151 }
152 Q.push(v);
153 }
154 }
155 }
156 }
157 }
158 }
159 }
160 }
161 return -1;
162 }
163
164 void compute(){
165 BS = map<Station, int>();
166 FS = map<Station, int>();
167 bfs(goal, BS, BACK);
168 cout << bfs(initial, FS, FORWARD) << endl;
169 }
170
171 bool input(){
172 int y;
173 cin >> nload >> y;
174 if ( nload == 0 && y == 0 ) return false;
175
176 for ( int i = 0; i < nload; i++ ){
177 for ( int j = 0; j < nload; j++ ){
178 M[i][WEST][j][WEST] = false;
179 M[i][WEST][j][EAST] = false;
180 M[i][EAST][j][WEST] = false;
181 M[i][EAST][j][EAST] = false;
182 }
183 }
184 int sl, tl;
185 char sd, td;
186 for ( int i = 0; i < y; i++ ){
187 cin >> sl >> sd >> tl >> td;
188 M[sl][(sd == 'W' ? WEST : EAST)][tl][(td == 'W' ? WEST : EAST)] = true;
189 M[tl][(td == 'W' ? WEST : EAST)][sl][(sd == 'W' ? WEST : EAST)] = true;
190 }
191
192 initial = Station(nload);
193 goal = Station(nload);
194
195 string train;
196 for ( int i = 0; i < nload; i++ ) {
197 cin >> train; if ( train == "-" ) train = "";
198 initial.loads[i] = Load(train);
199 }
200 for ( int i = 0; i < nload; i++ ) {
201 cin >> train; if ( train == "-" ) train = "";
202 goal.loads[i] = Load(train);
203 }
204
205 return true;
206 }
207
208 main(){
209 while( input() ) compute();
210 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |