Submission #691248
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}
const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;
int T, n, m;
int main(int argc, char *argv[]){
ios::sync_with_stdio(false);
cin >> n >> m;
int sx, sy, tx, ty;
cin >> sy >> sx >> ty >> tx; tx --; ty--; sx --; sy--;
string s(n*m, '#');
REP(i, n)REP(j, m) cin >> s[i*m+j];
queue<int> q;
int d[4] = {1, -1, m, -m};
q.push(sy*m+sx);
vi dp(n*m, INF);
dp[sy*m+sx] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
cout << u << ": " << dp[u] << endl;
REP(k, 4){
int v = u + d[k];
if(s[v] == '.' && chmin(dp[v], dp[u] + 1))
q.push(v);
}
}
cout << dp[ty*m+tx] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 幅優先探索 |
User |
zerokugi |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2498 Byte |
Status |
WA |
Exec Time |
18 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
WA |
4 ms |
256 KB |
subtask0_sample02.txt |
WA |
4 ms |
256 KB |
subtask0_sample03.txt |
WA |
18 ms |
256 KB |
subtask1_01.txt |
WA |
11 ms |
256 KB |
subtask1_02.txt |
WA |
11 ms |
256 KB |
subtask1_03.txt |
WA |
11 ms |
256 KB |
subtask1_04.txt |
WA |
18 ms |
256 KB |
subtask1_05.txt |
WA |
18 ms |
256 KB |
subtask1_06.txt |
WA |
15 ms |
256 KB |
subtask1_07.txt |
WA |
4 ms |
256 KB |
subtask1_08.txt |
WA |
6 ms |
256 KB |
subtask1_09.txt |
WA |
12 ms |
256 KB |
subtask1_10.txt |
WA |
6 ms |
256 KB |
subtask1_11.txt |
WA |
18 ms |
256 KB |
subtask1_12.txt |
WA |
17 ms |
256 KB |
subtask1_13.txt |
WA |
12 ms |
256 KB |
subtask1_14.txt |
WA |
4 ms |
256 KB |
subtask1_15.txt |
WA |
13 ms |
256 KB |
subtask1_16.txt |
WA |
12 ms |
256 KB |
subtask1_17.txt |
WA |
15 ms |
256 KB |
subtask1_18.txt |
WA |
14 ms |
256 KB |
subtask1_19.txt |
WA |
12 ms |
256 KB |
subtask1_20.txt |
WA |
12 ms |
256 KB |
subtask1_21.txt |
WA |
13 ms |
256 KB |
subtask1_22.txt |
WA |
12 ms |
256 KB |