2009-05-06
SRM223 Div1 Hard: RevolvingDoor
Algorithm Tutorials: How To Find a Solution (by Dumitru) より
- 1000点問題！
- マップ上のSからEまで行くのに、回転ドアを最低何回回転させる必要があるか。(辿り着けない場合は-1)
- 確かにBFSであります
- ドアの回転状態を持ち回る必要がある。listとか使うか?
- 問題よく読め！ドアは最大10個しかない！10bit！
- １つ回転数を少なく答えるケースがある・・・ゴールにドアがかぶっている場合にドアの状態を反映していなかった
- 時間かかったけどとりあえず全テストケース通るようになった！
- submit ... 317.84points (146'39'')
- 本番は３問で75分なんですけど＞＜
- しかしFailed System Test: TLE×1
"S ", " ", " ", "-O--O--O--O--O--O--O--O--O--O- ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " #", " #E"
- 確かにこれはゴールできないw
- ドアぐるぐる回しながら全ての状態(50x50x2^10)を走査することになるだろう
- ステップ数数え始める前に、ドア無視してflood fillしておくか
- どうやるんだっけ...queueだと重複あってなかなか進まない。set使うか
- できた
- →Passed System Test
- 最終的なコード:
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define found(s,e) ((s).find(e)!=(s).end())
class RevolvingDoors {
int w,h;
inline int cell(int x,int y){return (y<<6)|x;}
inline int cellx(int c){return c&63;}
inline int celly(int c){return c>>6;}
inline int left(int c){return c-1;}
inline int right(int c){return c+1;}
inline int up(int c){return c-64;}
inline int down(int c){return c+64;}
public:
int turns(vector<string> m) {
h=sz(m),w=sz(m[0]);
vector<bool> road(4096,false);
vector<vector<int> > score(4096);
vector<int> doors, doormap(4096,-1), doorof(4096,-1);
int doorcnt=0, start_cell=0, end_cell=0;
// pass1
rep(y,h){
rep(x,w){
int c=cell(x+1,y+1);
switch(m[y][x]){
case 'S': road[c]=true; start_cell=c; break;
case 'E': road[c]=true; end_cell=c; break;
case 'O': road[c]=false; doormap[c]=doorcnt++; doors.pb(c); break;
case '-': road[c]=true; break;
case '|': road[c]=true; break;
case '#': road[c]=false; break;
case ' ': road[c]=true; break;
}
}
}
int nm=1<<doorcnt;
rep(i,4096){
score[i].resize(nm); rep(j,nm) score[i][j]=INT_MAX;
}
int doorstat = 0;
// pass2
rep(y,h){
rep(x,w){
int c=cell(x+1,y+1), r,l,u,d,did=-1;
switch(m[y][x]){
case 'O': case '#': break;
case '-':
r=right(c),l=left(c);
if(doormap[r]>=0) did=doormap[r];
else if(doormap[l]>=0) did=doormap[l];
doorof[c]=did;
// doorstat |= (1 << did);
break;
case '|':
u=up(c),d=down(c);
if(doormap[u]>=0) did=doormap[u];
else if(doormap[d]>=0) did=doormap[d];
doorof[c]=did;
doorstat |= (1 << did);
break;
case ' ': case 'S': case 'E':
r=right(c),l=left(c),u=up(c),d=down(c);
if(doormap[r]>=0) did=doormap[r];
else if(doormap[l]>=0) did=doormap[l];
else if(doormap[u]>=0) did=doormap[u];
else if(doormap[d]>=0) did=doormap[d];
doorof[c]=did;
break;
}
}
}
// check impasse: flood fill (あとから追加)
vector<bool> reach(4096,false);
set<int> s0;
s0.insert(start_cell); // reach[start_cell]=true;
while(!s0.empty()){
typeof(s0.begin()) it = s0.begin();
int c=*it; s0.erase(it);
reach[c]=true;
if (c==end_cell) break;
printf(" I %d %d¥n", cellx(c),celly(c));
int nxt[4] = { up(c), right(c), down(c), left(c) };
rep(i,4){
int c_=nxt[i];
if(!road[c_]) continue;
if(!reach[c_]) s0.insert(c_);
}
}
if(!reach[end_cell]) return -1;
// let's探索
priority_queue<pair<int,pair<int,int> > > pq; // -score,loc,doorstat
pq.push(make_pair(0,make_pair(start_cell,doorstat)));
vector<int> goaled; int goaled_min=INT_MAX;
while(!pq.empty()){
pair<int,pair<int,int> > p=pq.top(); pq.pop();
int sc=-p.first, c=p.second.first, ds=p.second.second;
if (sc>goaled_min) break;
if (score[c][ds]<=sc) continue;
score[c][ds]=sc;
if(c==end_cell) {
if (sc<goaled_min) {
goaled_min=sc; goaled.pb(sc); }
continue;
}
int nxt[4] = { up(c), right(c), down(c), left(c) };
rep(i,4){
int c_=nxt[i];
if(!road[c_]) continue;
int did=doorof[c_];
if(did>=0){ // ドアな可能性あり
int dcell=doors[did], ofs=c_-dcell; if(ofs<0) ofs=-ofs;
int mask=1<<did;
int st=ds & mask;
if(st && ofs==64) { // |
if (c-c_ != c_-dcell){ //回転出来る
pq.push(make_pair(-(sc+1),make_pair(c_,ds-mask)));
}
} else if(!st && ofs==1){ // -
if (c-c_ != c_-dcell){ //回転出来る
pq.push(make_pair(-(sc+1),make_pair(c_,ds+mask)));
}
} else {
// ドアなし
pq.push(make_pair(-sc,make_pair(c_,ds)));
}
}else{
pq.push(make_pair(-sc,make_pair(c_,ds)));
}
}
}
if(sz(goaled) > 0){
sort(all(goaled));
return goaled[0];
} else {
return -1;
}
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090506