読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

ABC007_C

幅優先探索の問題
queueにいれて順番に計算していく.
座標を扱う際にtypedefが便利

typedef pair<int,int> P;
que.push(P(x,y));
#include <bits/stdc++.h>
using namespace std;
int r,c,sx,sy,gx,gy;
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
static const int MAX_R =50;
static const int INF = 1<<21;
char M[MAX_R][MAX_R+1];
int D[MAX_R][MAX_R];
typedef pair<int,int> P;

int main()
{
    queue<P> que;
    cin>>r>>c>>sy>>sx>>gy>>gx;
    sy--;sx--;gy--;gx--;
    string tmp;
    for(int y=0;y<r;y++){
        cin>>tmp;
        for(int x=0;x<c;x++){
            M[y][x] = tmp[x];
            D[y][x] = INF;
        }
    }
    D[sy][sx] = 0;
    que.push(P(sx,sy));
    while(!que.empty()){
        P p = que.front();que.pop();
        int x = p.first;
        int y = p.second;
        if(x==gx && y==gy)break;
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<c && 0<=ny && ny<r && M[ny][nx]=='.' && D[ny][nx]==INF){
                que.push(P(nx,ny));
                D[ny][nx] = D[y][x] + 1;
            }    
        }
    }
    cout<<D[gy][gx]<<endl;
    return 0;
}