Submission #691216
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef ostringstream OSS; typedef istringstream ISS;
typedef long long LL;
typedef pair<int, int> PII; typedef pair<LL, LL> PLL;
typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<VVI> VVVI;
typedef vector<LL> VLL; typedef vector<VLL> VVLL; typedef vector<VVLL> VVVLL;
typedef vector<double> VD; typedef vector<VD> VVD; typedef vector<VVD> VVVD;
typedef vector<string> VS; typedef vector<VS> VVS; typedef vector<VVS> VVVS;
typedef vector<bool> VB; typedef vector<VB> VVB; typedef vector<VVB> VVVB;
typedef vector<PII> VPII; typedef vector<VPII> VVPII; typedef vector<VVPII> VVVPII;
typedef vector<PLL> VPLL; typedef vector<VPLL> VVPLL; typedef vector<VVPLL> VVVPLL;
typedef unsigned int UI;
typedef vector<UI> VUI;
typedef vector<VUI> VVUI;
#define fst first
#define snd second
// #define Y first
// #define X second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define RANGEBOX(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define RANGE(x, l, r) ((l) <= (x) && (x) <= (r))
#define rep(i, N) for (int i = 0; i < (int)(N); i++)
#define rrep(i, N) for (int i = N - 1; i >= 0; i--)
#define REP(i, init, N) for (int i = (init); i < (int)(N); i++)
#define RREP(i, N, last) for (int i = (init - 1); i >= last; i--)
#define MAXUD(orig, target) orig = max(orig, target)
#define MINUD(orig, target) orig = min(orig, target)
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a) { OSS oss; oss << a; return oss.str(); };
template<typename T=int> inline void dump(vector<T> vs, bool ent=false) { rep(i, vs.size()) cout << vs[i] << (i+1==vs.size() ? '\n' : ' '); if (ent) cout << endl; }
template<typename T = int> inline void dump(vector<vector<T>> vs, bool ent = false) { rep(i, vs.size()) dump<T>(vs[i]); if (ent) cout << endl; }
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 0x3f3f3f3f;
const int DX[] = {1, 0, -1, 0};
const int DY[] = {0, -1, 0, 1};
const double EPS = 1e-12;
// const double PI = acos(-1.0);
// lambda: [](T1 x)->T2{return y;}
// simple lambda: [](T x){return x;}
int main(void) {
int H, W;
cin >> H >> W;
PII s, g;
cin >> s.fst >> s.snd >> g.fst >> g.snd;
--s.fst; --s.snd; --g.fst; --g.snd;
VS ts(H);
rep(i, H) cin >> ts[i];
VVI dists(H, VI(W, INF));
dists[s.fst][s.snd] = 0;
queue<PII> q;
q.push(s);
while(q.size()) {
int y = q.front().fst;
int x = q.front().snd;
q.pop();
rep(i, 4) {
int ny = y + DY[i];
int nx = x + DX[i];
if (!RANGEBOX(nx, ny, W, H)) continue;
if (ts[ny][nx] == '#') continue;
if (dists[ny][nx] != INF) continue;
dists[ny][nx] = dists[y][x] + 1;
q.push(MP(ny, nx));
}
}
cout << dists[g.fst][g.snd] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 幅優先探索 |
User |
snakazawa |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3309 Byte |
Status |
AC |
Exec Time |
6 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
All |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
4 ms |
256 KB |
subtask0_sample02.txt |
AC |
4 ms |
256 KB |
subtask0_sample03.txt |
AC |
4 ms |
256 KB |
subtask1_01.txt |
AC |
4 ms |
256 KB |
subtask1_02.txt |
AC |
4 ms |
256 KB |
subtask1_03.txt |
AC |
4 ms |
256 KB |
subtask1_04.txt |
AC |
4 ms |
256 KB |
subtask1_05.txt |
AC |
4 ms |
256 KB |
subtask1_06.txt |
AC |
4 ms |
256 KB |
subtask1_07.txt |
AC |
4 ms |
256 KB |
subtask1_08.txt |
AC |
4 ms |
256 KB |
subtask1_09.txt |
AC |
4 ms |
256 KB |
subtask1_10.txt |
AC |
4 ms |
256 KB |
subtask1_11.txt |
AC |
4 ms |
256 KB |
subtask1_12.txt |
AC |
4 ms |
256 KB |
subtask1_13.txt |
AC |
4 ms |
256 KB |
subtask1_14.txt |
AC |
4 ms |
256 KB |
subtask1_15.txt |
AC |
4 ms |
256 KB |
subtask1_16.txt |
AC |
4 ms |
256 KB |
subtask1_17.txt |
AC |
5 ms |
256 KB |
subtask1_18.txt |
AC |
6 ms |
256 KB |
subtask1_19.txt |
AC |
4 ms |
256 KB |
subtask1_20.txt |
AC |
4 ms |
256 KB |
subtask1_21.txt |
AC |
4 ms |
256 KB |
subtask1_22.txt |
AC |
4 ms |
256 KB |