Submission #814574

#TimeUsernameProblemLanguageResultExecution timeMemory
814574devariaotaTracks in the Snow (BOI13_tracks)C++17
34.38 / 100
2094 ms78820 KiB
#include <bits/stdc++.h> using namespace std; int h, w, total; int meadow[4005][4005]; bool vis[4005][4005]; // vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int main() { cin >> h >> w; char in; for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { cin >> in; if (in == '.') { meadow[i][j] = -1; } else if (in == 'R') { meadow[i][j] = 1; total++; } else { meadow[i][j] = 0; total++; } } } // for (int i = 1; i <= h; i++) { // for (int j = 1; j <= w; j++) { // cout << meadow[i][j] << " "; // } // cout << endl; // } int ans = 0; while (true) { queue<pair<int, int>> q; memset(vis, 0, sizeof(vis)); q.push({1, 1}); vis[1][1] = 1; int row, col, count = 1; int top = meadow[1][1]; meadow[1][1] += 1; meadow[1][1] %= 2; ans++; while (!q.empty()) { row = q.front().first; col = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { if (row + dir[i][0] > 0 and row + dir[i][0] <= h and col + dir[i][1] > 0 and col + dir[i][1] <= w and !vis[row+dir[i][0]][col+dir[i][1]] and meadow[row+dir[i][0]][col+dir[i][1]] == top) { q.push({row+dir[i][0], col+dir[i][1]}); meadow[row+dir[i][0]][col+dir[i][1]] += 1; meadow[row+dir[i][0]][col+dir[i][1]] %= 2; vis[row+dir[i][0]][col+dir[i][1]] = 1; count++; } } } // for (int i = 1; i <= h; i++) { // for (int j = 1; j <= w; j++) { // cout << meadow[i][j] << " "; // } // cout << endl; // } // cout << count << " " << total << endl; // cout << endl; // break; if (count == total) { cout << ans << endl; return 0; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...