3984:迷宫问题

keyword

幅優先探索　C++

概要

5*5の迷路が与えられる。スタートからゴールまでの最短経路を出力する問題。
息抜き問題。

int board[5][5];
pair<int,int> prev[5][5];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};


void solve(){
    queue<pair<int,int> > Q;
    Q.push(make_pair(0,0));
    board[0][0] = true;
    while(!Q.empty()){
        pair<int,int> tp = Q.front(); Q.pop();
        for(int k=0; k<4; k++){
            int ny = tp.first + dy[k],
                   nx = tp.second + dx[k];
            if(0 <= ny && ny < 5 && 0 <= nx && nx < 5 && !board[ny][nx]){
                board[ny][nx] = 1;
                prev[ny][nx] = tp;
                Q.push(make_pair(ny,nx));
            }
        }
    }
    vector<pair<int,int> > ans;
    pair<int,int> cur = make_pair(4,4);
    ans.push_back(cur);
    while(1){
        cur = prev[cur.first][cur.second];
        ans.push_back(cur);
        if(cur == make_pair(0,0))
            break;
    }
    while(!ans.empty()){
        printf("(%d, %d)\n", ans.back().first, ans.back().second);
        ans.pop_back();
    }
}