제출 #1235545

#제출 시각아이디문제언어결과실행 시간메모리
1235545jiayiiyaijTracks in the Snow (BOI13_tracks)C++17
58.44 / 100
2098 ms79096 KiB
#include <iostream> #include <vector> #include<queue> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; cin.ignore(); vector<vector<char>> mapp(H, vector<char>(W)); for (int i=0; i<H; i++) { string line; cin >> line; for (int j=0; j<W; j++) { mapp[i][j] = line[j]; } } vector<char> ani(2, '.'); if (mapp[0][0] == 'R') ani = {'R', 'F'}; else ani = {'F', 'R'}; int dirs[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} }; int count = 0; bool flag0 = false, flag1 = false; vector<vector<int>> vis(H, vector<int>(W, 0)); int vid = 1; // visit ID trick while(true) { flag0 = false; flag1 = false; deque<pair<int, int>> q; q.push_back({0,0}); vis[0][0] = vid; while (!q.empty()) { auto [r, c] = q.front(); q.pop_front(); for (int i = 0; i < 4; i++) { int rr = r + dirs[i][0]; int cc = c + dirs[i][1]; if (rr < 0 || rr >= H || cc < 0 || cc >= W) continue; if (vis[rr][cc] == vid) continue; if (mapp[rr][cc] == '.') continue; if (mapp[r][c] == ani[0] || mapp[r][c] == '#') { if (mapp[rr][cc] == ani[0] || mapp[r][c] == ani[0]) flag0 = true; if (mapp[rr][cc] == ani[1]) flag1 = true; q.push_back({rr, cc}); vis[rr][cc] = vid; } if (mapp[r][c] == ani[1]) { if (mapp[rr][cc] == ani[1] || mapp[rr][cc] == '#') { q.push_back({rr, cc}); vis[rr][cc] = vid; } } } mapp[r][c] = '#'; } if (not flag0) break; count += 1; if (not flag1) break; count += 1; vid++; } cout << count << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...