Submission #2548621
Source Code Expand
/* main code starts from line 130. */ /* ---------- STL Libraries ---------- */ // IO library #include <cstdio> #include <iomanip> #include <ios> #include <iostream> // algorithm library #include <algorithm> #include <cmath> #include <numeric> // container library #include <bitset> #include <map> #include <queue> #include <set> #include <string> #include <vector> /* ---------- Namespace ---------- */ using namespace std; /* ---------- Type Abbreviation ---------- */ template <typename T> using V = vector<T>; template <typename T, typename U> using P = pair<T, U>; template <typename T> using PQ = priority_queue<T>; template <typename T> using GPQ = priority_queue<T, V<T>, greater<T>>; using ll = long long; using str = string; #define fst first #define snd second #define pb push_back #define mp make_pair #define mt make_tuple /* ---------- conversion ---------- */ #define INT(c) static_cast<int>(c) #define CHAR(n) static_cast<char>(n) #define LL(n) static_cast<ll>(n) #define DOUBLE(n) static_cast<double>(n) /* ---------- container ---------- */ #define ALL(v) (v).begin(), (v).end() #define SIZE(v) (LL((v).size())) #define FIND(v, k) (v).find(k) != (v).end() #define VFIND(v, k) find(ALL(v), k) != (v).end #define SORT(v) sort(ALL(v)) #define GSORT(v) sort(ALL(v), greater<decltype((v).front())>()) /* ---------- repetition ---------- */ #define FOR(i, a, b) for (ll i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define NREP(i, n) FOR(i, 1, n + 1) #define RFOR(i, a, b) for (ll i = (a); i >= (b); i--) #define RREP(i, n) RFOR(i, n - 1, 0) #define RNREP(i, n) RFOR(i, n, 1) // Usual REP runs from 0 to n-1 (R: n-1 to 0) // Natural REP runs from 1 to n (R: n to 1) /* ---------- Short Functions ---------- */ template <typename T> T sq(T a) { return a * a; } #define fcout cout << fixed << setprecision(10) /* ----------- debug ---------- */ template <typename T, typename U> void testP2(T a, U b) { cout << "(" << a << ", " << b << ")" << endl; return; } template <typename T> void testV(T v) { cout << "["; for (auto i : v) { cout << i << ", "; } cout << "\b\b]" << endl; return; } template <typename T> void testV2(T v) { for (auto sv : v) { testV(sv); } cout << endl; return; } #define GET_VAR_NAME(variable) #variable #define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl; #define testP(p) \ cout << GET_VAR_NAME(p) << " = "; \ testP2(p.fst, p.snd); /* ---------- Constants ---------- */ // const ll MOD = 1e9 + 7; const int INF = 1 << 25; // const ll INF = 1LL << 50; // const double PI = 3.14159265358979; const ll dx[4] = {0, -1, 1, 0}; const ll dy[4] = {-1, 0, 0, 1}; // const ll dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; // const ll dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; /* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */ /* ---------- Type Definition ----------- */ /* ---------- Global Variance ----------- */ /* ------------- Functions -------------- */ /* ----------- Main Function ------------ */ int main() { cin.tie(0); ios::sync_with_stdio(false); int H, W; cin >> H >> W; P<int, int> s = mp(0, 0), g = mp(0, 0); V<string> c(H); REP(i, H) { cin >> c[i]; REP(j, W) { if (c[i][j] == 's') { s = mp(i, j); } else if (c[i][j] == 'g') { g = mp(i, j); } } } GPQ<P<int, P<int, int>>> que; V<V<int>> dp(H, V<int>(W, INF)); que.push(mp(0, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int cost = p.fst; P<int, int> place = p.snd; if (dp[place.fst][place.snd] <= cost) continue; dp[place.fst][place.snd] = cost; REP(i, 4) { int x = place.fst + dx[i]; int y = place.snd + dy[i]; if (x < 0 || x >= H || y < 0 || y >= W) continue; if (c[x][y] == '#') { que.push(mp(cost + 1, mp(x, y))); } else { que.push(mp(cost, mp(x, y))); } } } // testV2(dp); if (dp[g.fst][g.snd] <= 2) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 器物損壊!高橋君 |
User | Tiramister |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 4470 Byte |
Status | AC |
Exec Time | 195 ms |
Memory | 6136 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_min_01.txt | AC | 1 ms | 256 KB |
00_min_02.txt | AC | 1 ms | 256 KB |
00_min_03.txt | AC | 1 ms | 256 KB |
00_min_04.txt | AC | 1 ms | 256 KB |
00_min_05.txt | AC | 1 ms | 256 KB |
00_min_06.txt | AC | 1 ms | 256 KB |
00_min_07.txt | AC | 1 ms | 256 KB |
00_min_08.txt | AC | 1 ms | 256 KB |
00_sample_01.txt | AC | 1 ms | 256 KB |
00_sample_02.txt | AC | 1 ms | 256 KB |
00_sample_03.txt | AC | 1 ms | 256 KB |
00_sample_04.txt | AC | 1 ms | 256 KB |
00_sample_05.txt | AC | 1 ms | 256 KB |
01_rnd_00.txt | AC | 113 ms | 1664 KB |
01_rnd_01.txt | AC | 150 ms | 3196 KB |
01_rnd_02.txt | AC | 191 ms | 4728 KB |
01_rnd_03.txt | AC | 112 ms | 1792 KB |
01_rnd_04.txt | AC | 153 ms | 3196 KB |
01_rnd_05.txt | AC | 164 ms | 1860 KB |
01_rnd_06.txt | AC | 187 ms | 5624 KB |
01_rnd_07.txt | AC | 188 ms | 4728 KB |
01_rnd_08.txt | AC | 125 ms | 1664 KB |
01_rnd_09.txt | AC | 150 ms | 1664 KB |
01_rnd_10.txt | AC | 193 ms | 4728 KB |
01_rnd_11.txt | AC | 118 ms | 1664 KB |
01_rnd_12.txt | AC | 171 ms | 4728 KB |
01_rnd_13.txt | AC | 173 ms | 5752 KB |
01_rnd_14.txt | AC | 189 ms | 3196 KB |
01_rnd_15.txt | AC | 191 ms | 4728 KB |
01_rnd_16.txt | AC | 120 ms | 1664 KB |
01_rnd_17.txt | AC | 194 ms | 6136 KB |
01_rnd_18.txt | AC | 133 ms | 1664 KB |
01_rnd_19.txt | AC | 125 ms | 2116 KB |
02_rndhard_00.txt | AC | 188 ms | 3196 KB |
02_rndhard_01.txt | AC | 187 ms | 3196 KB |
02_rndhard_02.txt | AC | 192 ms | 3196 KB |
02_rndhard_03.txt | AC | 190 ms | 3196 KB |
02_rndhard_04.txt | AC | 195 ms | 4728 KB |
02_rndhard_05.txt | AC | 194 ms | 4728 KB |
02_rndhard_06.txt | AC | 194 ms | 3196 KB |
02_rndhard_07.txt | AC | 194 ms | 3196 KB |
02_rndhard_08.txt | AC | 193 ms | 3196 KB |
02_rndhard_09.txt | AC | 190 ms | 3196 KB |
02_rndhard_10.txt | AC | 186 ms | 3196 KB |
02_rndhard_11.txt | AC | 186 ms | 3196 KB |
02_rndhard_12.txt | AC | 180 ms | 2432 KB |
02_rndhard_13.txt | AC | 180 ms | 2432 KB |
02_rndhard_14.txt | AC | 190 ms | 3196 KB |
02_rndhard_15.txt | AC | 190 ms | 3196 KB |
02_rndhard_16.txt | AC | 195 ms | 5880 KB |
02_rndhard_17.txt | AC | 192 ms | 4728 KB |
02_rndhard_18.txt | AC | 187 ms | 3196 KB |
02_rndhard_19.txt | AC | 188 ms | 3196 KB |
02_rndhard_20.txt | AC | 187 ms | 3196 KB |
02_rndhard_21.txt | AC | 187 ms | 3196 KB |
02_rndhard_22.txt | AC | 188 ms | 3196 KB |
02_rndhard_23.txt | AC | 186 ms | 3196 KB |
02_rndhard_24.txt | AC | 194 ms | 4728 KB |
02_rndhard_25.txt | AC | 193 ms | 4728 KB |
02_rndhard_26.txt | AC | 187 ms | 3196 KB |
02_rndhard_27.txt | AC | 186 ms | 3196 KB |
02_rndhard_28.txt | AC | 180 ms | 2432 KB |
02_rndhard_29.txt | AC | 182 ms | 2432 KB |
02_rndhard_30.txt | AC | 172 ms | 2116 KB |
02_rndhard_31.txt | AC | 171 ms | 2116 KB |
02_rndhard_32.txt | AC | 192 ms | 3196 KB |
02_rndhard_33.txt | AC | 192 ms | 3196 KB |
02_rndhard_34.txt | AC | 195 ms | 5752 KB |
02_rndhard_35.txt | AC | 192 ms | 3196 KB |
02_rndhard_36.txt | AC | 190 ms | 3196 KB |
02_rndhard_37.txt | AC | 191 ms | 3196 KB |
02_rndhard_38.txt | AC | 192 ms | 3196 KB |
02_rndhard_39.txt | AC | 191 ms | 3196 KB |
03_rndhardsmall_00.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_01.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_02.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_03.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_04.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_05.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_06.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_07.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_08.txt | AC | 1 ms | 256 KB |
03_rndhardsmall_09.txt | AC | 1 ms | 256 KB |