# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
867772 | 2023-10-29T12:49:58 Z | BoopyTheNoob | Tracks in the Snow (BOI13_tracks) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; int dx[4]{1, -1, 0, 0}, int dy[4]{0, 0, 1, -1}; int N, M, dist[4000][4000], ans = 1; string grid[4000]; int main (void) { iostream::sync_with_stdio(false); cin.tie(0); cin >> N >> M; //vector<string> grid(N); for (int i = 0; i < N; i++) cin >> grid[i]; //vector<vector<int>> dist(N, vector<int>(M, 0)); deque<pair<int, int>> bfs; bfs.push_back({0, 0}); dist[0][0] = 1; while (!bfs.empty()) { int x = bfs.front().first, y = bfs.front().second; bfs.pop_front(); ans = max(ans, dist[x][y]); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; /*if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if (dist[nx][ny] != 0 || grid[nx][ny] == '.') continue; pair<int, int> next = {nx, ny}; if (grid[x][y] != grid[nx][ny]) { dist[nx][ny] = dist[x][y] + 1; bfs.push_back({nx, ny}); } else { dist[nx][ny] = dist[x][y]; bfs.push_front({nx, ny}); }*/ if (nx >= 0 && nx < N && ny >= 0 && ny < M && grid[nx][ny] != '.' && dist[nx][ny] == 0) { if (grid[nx][ny] != grid[x][y]) { dist[nx][ny] = dist[x][y] + 1; bfs.push_back({nx, ny}); } else { dist[nx][ny] = dist[x][y]; bfs.push_front({nx, ny}); } } } } /*for (auto x: dist) { for (auto y: x) { cout << y << " "; } cout << endl; }*/ cout << ans; return 0; }