제출 #575750

#제출 시각아이디문제언어결과실행 시간메모리
575750acatmeowmeowTracks in the Snow (BOI13_tracks)C++11
2.19 / 100
923 ms277236 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 4e3 + 5; int n, m, d[N][N], rab = 0, fox = 0; char grid[N][N]; vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1}; deque<pair<int, pair<int, int>>> dq; bool inbound(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m && grid[x][y] != '.'; } void bfs() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { d[i][j] = 1e18; } } dq.push_front({1, {1, 1}}); d[1][1] = 1; while (dq.size()) { int p = dq.front().first, x = dq.front().second.first, y = dq.front().second.second; dq.pop_front(); if (p != d[x][y]) continue; for (int k = 0; k < 4; k++) { int tox = x + dx[k], toy = y + dy[k]; if (!inbound(tox, toy)) continue; int c = grid[x][y] != grid[tox][toy]; if (d[tox][toy] <= d[x][y] + c) continue; d[tox][toy] = d[x][y] + c; if (c) dq.push_back({d[tox][toy], {tox, toy}}); else dq.push_front({d[tox][toy], {tox, toy}}); } } cout << max(d[n][m], rab + fox) << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> grid[i][j]; if (grid[i][j] == 'R') rab = 1; if (grid[i][j] == 'F') fox = 1; } } bfs(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...