Submission #850432

#	Time	Username	Problem	Language	Result	Execution time	Memory
850432		thisistotallymyusername	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	448 ms	135200 KiB

tracks

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

typedef pair<int, int> PII;
#define F first
#define S second

const int N = 4010, INF = 0x3f3f3f3f;

char g[N][N];
int n, m, res, d[N][N], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

void bfs() {
    deque<PII> q; q.emplace_back(0, 0);
    memset(d, 0x3f, sizeof d); d[0][0] = 1;
    while (!q.empty()) {
        PII t = q.front(); q.pop_front();
        for (int i = 0; i < 4; i++) {
            int x = t.F + dx[i], y = t.S + dy[i];
            if (0 <= x && x < n && 0 <= y && y < m && g[x][y] != '.') {
                int tmp = (g[x][y] != g[t.F][t.S]);
                if (d[x][y] > d[t.F][t.S] + tmp) {
                    d[x][y] = d[t.F][t.S] + tmp;
                    if (tmp) {
                        q.emplace_back(x, y);
                    } else {
                        q.emplace_front(x, y);
                    }
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", g[i]);
    bfs();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (d[i][j] != INF)
                res = max(res, d[i][j]);
    printf("%d\n", res);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
tracks.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     for (int i = 0; i < n; i++) scanf("%s", g[i]);
      |                                 ~~~~~^~~~~~~~~~~~

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