Submission #511187

#	Time	Username	Problem	Language	Result	Execution time	Memory
511187		DragosC1	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	612 ms	130868 KiB

tracks

#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;

#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

char a[4001][4001];
int dist[4001][4001];
int n, m;
int Max;

deque<pair<int, int>> Q;

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

bool inside(int i, int j) {
    if (i >= 1 && j >= 1 && i <= n && j <= m)
        return 1;
    return 0;
}

void bfs01(int istart, int jstart) {
    int i, j, inou, jnou, k;
    pair<int, int> p;
    Q.push_back({istart, jstart});
    dist[istart][jstart] = 1;
    while (!Q.empty()) {
        i = Q.front().first, j = Q.front().second;
        Q.pop_front();
        if (dist[i][j] > Max) {
            Max = dist[i][j];
        }
        for (k = 0; k < 4; k++) {
            inou = i + di[k], jnou = j + dj[k];
            if (inside(inou, jnou) && !dist[inou][jnou] && a[inou][jnou] != '.') 
                if (a[inou][jnou] == a[i][j]) {
                    Q.push_front({inou, jnou});
                    dist[inou][jnou] = dist[i][j];
                }
                else {
                    Q.push_back({inou, jnou});
                    dist[inou][jnou] = dist[i][j] + 1;
                }
        }
    }
}

int main() {
    fast
    int i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> a[i][j];
    bfs01(1, 1);
    cout << Max;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void bfs01(int, int)':
tracks.cpp:38:16: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   38 |             if (inside(inou, jnou) && !dist[inou][jnou] && a[inou][jnou] != '.')
      |                ^

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