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;
}