Submission #6926038

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
#include <time.h>
using namespace std;
#define pi pair<int,int>
#define pl pair<long long,long long>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

int dist[55][55];
void init(){
    for (int i = 0; i < 55; i++){
        for (int j = 0; j < 55; j++){
            dist[i][j] = MM;
        }
    }
}


int main(){
    int R,C,sy,sx,gy,gx; cin >> R >> C >> sy >> sx >> gy >> gx;
    char c[55][55];
    sy--,sx--,gy--,gx--;

    init();
    for (int i = 0; i < R; i++){
        for (int j = 0; j < C; j++){
            cin >> c[i][j];
        }
    }
    queue<pi> que;
    que.push({sy,sx});

    dist[sy][sx] = 0;
    while (que.size()){
        pi pf = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            int ny = pf.first + dy[i], nx = pf.second + dx[i];
            if (1 <= ny && ny <= R && 1 <= nx && nx <= C && c[ny][nx] == '.' && dist[ny][nx] == MM){
                dist[ny][nx] = dist[pf.first][pf.second] + 1;
                que.push({ny,nx});
            }
        }
    }

    /*
    for (int i = 0; i < R; i++){
        for (int j = 0; j < C; j++){
            if (dist[i][j] != MM) cout << dist[i][j] << " ";
            else cout << "MM" << " ";
        }
        cout << "\n";
    }
    */
    cout << dist[gy][gx] << endl;
}

Submission Info

Judge Result