AOJ 1156 Twirling Robot
問題
解法
BFSで解けます。priority_queue使ってコストの低いとこから見ていって、goalについたら答えです。
コード
int w, h; int s[32][32], dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, c[4], used[32][32][4]; int main(){ while(scanf("%d%d", &w, &h) && w+h){ rep(i, h) rep(j, w) scanf("%d", &s[i][j]); rep(i, 4) scanf("%d", c+i); memset(used, 0, sizeof(used)); priority_queue<pipi, vector<pipi>, greater<pipi> >q; // cost, nesw, y, x q.push(MP(MP(0, 1), MP(0, 0))); while(!q.empty()){ pipi now = q.top(); q.pop(); if(used[now.Y][now.X][now.F.S]++) continue; if(now.Y == h-1 && now.X == w- 1){ printf("%d\n", now.F.F); break; } rep(i, 4){ pipi next = now; if(i != s[now.Y][now.X]) next.F.F += c[i]; next.F.S = (next.F.S+i)%4; next.Y += dy[next.F.S]; next.X += dx[next.F.S]; if(next.Y < 0 || next.X < 0 || next.Y >= h || next.X >= w) continue; q.push(next); } } } return 0; }