aoj 0558 - Cheese

問題

問題概要

幅優先探索で最短経路を求める問題。ただしスタートとゴールがいくつもある。

解法

よくあるstartからgoalまでの最短経路を求める問題と同じ。ただし、その途中でチーズを小さい順に食べていかなければならない。そのため、（ciをチーズi番目とすると）c0(S)からc1の距離、c1からc2の距離、c2からc3の距離、、、ckからc(k+1)の距離、、、c(n-1)からcnの距離を順番に求めていき、その和を答えとして出力すればいい。
探索の具体的なやり方は、探索可能な座標をqueueに入れていき、そのマスカラ順番に4方向に動かしたマスを見ていく。一度通ったますを何度も通らないようにさらに、2点間最短経路も残しておくために、もう一つ配列を用意しておくこと。

ミス

チーズを食べないならその場所を通れるという記述を見逃していて、手間取った。

コード

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define fi first
#define se second
static const int INF = 1e9;
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
string board[1001];//入力用配列
int d[1001][1001];//どこを探索したかとそこまでの最短距離を入れる配列
int h, w, n;
pair<int, int> point[10];//fi=y座標 se=x座標
int ans = 0;
bool flag;
//幅優先探索
void bfs(void){
    rep(i, n){//スタートとゴールを
        int starty = point[i].fi, startx = point[i].se;//start
        int endy = point[i + 1].fi, endx = point[i + 1].se;//end
        queue<pair<int, int> > q;
        q.push(make_pair(starty, startx));//start時点を入れる
        rep(i, h) rep(j, w) d[i][j] = INF;//初期化
        d[starty][startx] = 0;
        flag = false;
        while(!q.empty()){
            pair<int, int> now;
            now = q.front(); q.pop();
            rep(j, 4){//4方向に動かす
                int y = now.fi + dy[j];
                int x = now.se + dx[j];
                if(y < 0 || h <= y || x < 0 || w <= x) continue;//範囲外
                if(d[y][x] == INF && board[y][x] != 'X'){
                    d[y][x] = d[now.fi][now.se] + 1;//最短距離を計算
                    q.push(make_pair(y, x));
                }
                if(y == endy && x == endx){
                    flag = true;
                    ans += d[y][x];//距離を足していく
                    break;
                }
            }
            if(flag == true) break;
        }
    }
    return;
}

int main(void){
    cin >> h >> w >> n;
    rep(i, h){
        cin >> board[i];
    }

    //start時点とチーズの場所を先に求めておく
    rep(i, h) rep(j, w){
        if(board[i][j] == 'S'){
            point[0].fi = i; point[0].se = j;
        }else if ('1' <= board[i][j] && board[i][j] <= '9'){
            int tmp = board[i][j] - '0';
            point[tmp].fi = i; point[tmp].se = j;
        }
    }
    bfs();
    cout << ans << endl;
    return 0;
}