Submission #1267257

#TimeUsernameProblemLanguageResultExecution timeMemory
1267257minhphanTracks in the Snow (BOI13_tracks)C++17
100 / 100
788 ms160696 KiB
#include <iostream> #include <deque> #include <vector> using namespace std; int dx[4]{0, 1, 0, -1}; int dy[4]{1, 0, -1, 0}; int main() { int H, W; cin >> H; cin >> W; vector<vector<int>> values(W, vector<int>(H, 0)); deque<pair<int,int>> q; q.emplace_back(0, 0); values[0][0] = 1; vector<vector<int>> grid(W, vector<int>(H, -1)); for (int i = 0; i<H; i++) { string line; cin >> line; for (int j = 0; j<W; j++) { if (line.at(j) == 'F') { grid[j][i] = 1; } else if (line.at(j) == 'R') { grid[j][i] = 0; } } } int solution = 1; while (!q.empty()) { const pair<int, int> el = q.front(); q.pop_front(); solution = max(solution, values[el.first][el.second]); for (int i = 0; i<4; i++) { const int x = el.first + dx[i]; const int y = el.second + dy[i]; if (x >= 0 && x<W && y>= 0 && y<H && values[x][y] == 0 && grid[x][y] != -1) { if (grid[el.first][el.second] == grid[x][y]) { q.emplace_front(x, y); values[x][y] = values[el.first][el.second]; } else { q.emplace_back(x, y); values[x][y] = values[el.first][el.second] + 1; } } } } cout << solution; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...