AOJ : 0557 - チーズ (Cheese)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0558&lang=jp
問題文が日本語なので, 説明省略.

アルゴリズム

幅優先探索で解けます.
(最初ダイクストラで解こうとかしてました)

問題文を読んだら, 1 -> 2 -> 3... と順番にチーズを食べていかないといけないことがわかります.

• S~1 の最短距離を幅優先で求めて, 答えに足しこみ.
• 1~2 の最短距離を幅優先で求めて, 答えに足しこみ.
• 2~3 の最短距離を幅優先で求めて, 答えに足しこみ.
• ...

全て食べ終わったら, 答えを出力.

プログラム

class P{
public:
  int x,y,cost;
  P(int _x,int _y,int _cost){...}
};

int h,w,n;
char t[1002][1002];
bool closed[1002][1002];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

P minDist(int x,int y,char to){
  queue<P> open;
  memset(closed,0,sizeof(closed));

  open.push(P(x,y,0));

  while(!open.empty()){
    P p = open.front(); open.pop();
    if(closed[p.x][p.y]) continue;
    closed[p.x][p.y] = true;

    if(t[p.y][p.x] == to){
      return p;
    }

    for(int i=0;i<4;i++){
      int nx = p.x + dx[i];
      int ny = p.y + dy[i];

      if(nx>=0 && nx<w && ny>=0 && ny<h && t[ny][nx]!='X'){
        open.push(P(nx,ny,p.cost+1));
      }
    }
  }
}

int main(void){
  cin>>h>>w>>n;

  int x,y;
  for(int i=0;i<h;i++){
    cin>>t[i];
    for(int j=0;j<w;j++){
      if(t[i][j] == 'S'){
        t[i][j] = '.';
        x = j;
        y = i;
      }
    }
  }

  int ans = 0;
  for(int i=1;i<=n;i++){
    P res = minDist(x,y,'0'+i);
    ans += res.cost;
    x = res.x;
    y = res.y;
  }
  cout<<ans<<endl;

  return 0;
}