スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。