제출 #675778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675778		aaggupta07	Tracks in the Snow (BOI13_tracks)	C++17	3.33 / 100	1611 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 4001
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define int long long

using pi = pair<int, int>;

int n, m, curC = 1;
string grid[MAX_N];
int visited[MAX_N][MAX_N];
set<int> adj[MAX_N];
int distances[MAX_N];

void floodfill(int r, int c, char color) {
    if(r < 0 || r >= n || c < 0 || c >= m || grid[r][c] == '.') return;
    if(grid[r][c] != color && visited[r][c]) {
        adj[curC-1].insert(visited[r][c]);
        adj[visited[r][c]-1].insert(curC-1);
        return;
    }
    else if(visited[r][c] || grid[r][c] != color) return;

    visited[r][c] = curC;
    floodfill(r+1, c, color);
    floodfill(r-1, c, color);
    floodfill(r, c+1, color);
    floodfill(r, c-1, color);
}

void bfs(int node) {
    queue<int> q;
    q.push(node);
    distances[node] = 1;

    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int i: adj[cur]) {
            if(distances[i] == 0) {
                distances[i] = distances[cur] + 1;
                q.push(i);
            }
        }
    }
}

signed main() {
    cin >> n >> m;
    for(int i = 0; i < n; ++i) cin >> grid[i];

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(visited[i][j] == 0 && grid[i][j] != '.') {
                floodfill(i, j, grid[i][j]);
                ++curC;
            }
        }
    }

    // for(int i = 0; i < n; ++i) cout << grid[i] << endl;
    // for(int i = 0; i < n; ++i) {for(int j = 0; j < m; ++j) cout << visited[i][j] << ' '; cout << endl;}

    /* for(int i = 0; i < n; ++i) {
        for(int j: adj[i]) cout << j << ' '; cout << endl;
    } */

    bfs(0);
    int maxDist = 1;
    for(int i = 0; i < n; ++i) {
        maxDist = max(maxDist, distances[i]);
    }
    cout << maxDist << '\n';
    return 0;
}

• Subtask 1: 3.3333333333333335 / 30
• Subtask 2: 0 / 70