Submission #1268771

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <chrono>
#include <sstream>
#include <iomanip>
using namespace std;
#define MOD          1000000007
#define PI           3.14159265358979
#define rep(i, n)    for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r) for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)   for (auto i : v)
#define all(x)       (x).begin(), (x).end()
#define rall(x)      (x).rbegin(), (x).rend()
#define pb(x)        push_back(x)
#define mp(x, y)     make_pair((x), (y))
#define fi           first
#define se           second
#define setp(x)      setprecision(x)
#define mset(m, v)   memset(m, v, sizeof(m))
//#define int          long long
//static const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
static const int INF =        0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef long long             ll;
typedef vector<int>           vi;
typedef vector<double>        vd;
typedef vector<long long>     vll;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef pair<int, int>        pii;
typedef pair<long, long>      pll;
typedef vector<pii>           vpii;
typedef vector<pll>           vpll;
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }

struct state { int y, x, step; };
static const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int main() { 
        int h, w, sy, sx, gy, gx;
        cin >> h >> w >> sy >> sx >> gy >> gx;
        sy --;
        sx --;
        gy --;
        gx --;
        string M[100];
        rep(i, h) cin >> M[i];
        vector<vector<bool>> used(h, vector<bool>(w, false));
        queue<state> q;
        q.push({sy, sx, 0});
        int ans;
        while (!q.empty()) {
                state p = q.front(); q.pop();
                if (p.y == gy && p.x == gx) {
                        ans = p.step;
                        break;
                }
                rep(dd, 4) {
                        int xx = p.x + dx[dd], yy = p.y + dy[dd];
                        if (xx < 0 || xx >= w || yy < 0 || yy >= h) continue;
                        else if (!used[yy][xx] && M[yy][xx] == '.') {
                                used[yy][xx] = true;
                                q.push({yy, xx, p.step + 1});
                        }
                }
        }
        cout << ans << endl;
        return 0;
}

Submission Info

Judge Result