Submission #1166783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166783		anomori	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	537 ms	118968 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

/*
ifstream fin("input.in");
ofstream fout("output.out");
*/
#define fin cin
#define fout cout

using ll = long long;
const int nmax = 4001;

struct point {int x,y;};

int n,m;
char mat[nmax][nmax];
int depth[nmax][nmax];
deque<point> dq;

const point d[] = {
        {1,0},
        {0,1},
        {-1,0},
        {0,-1}
};

bool inside(int x, int y) {
    return 1 <= x and x <= n
       and 1 <= y and y <= m
       and mat[x][y] != '.';
}

int main() {
    ios_base::sync_with_stdio(false);
    fin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) fin >> mat[i][j];
    dq.push_back({1,1});

    depth[1][1] = 1;

    int ans = 0;

    while (!dq.empty()) {
        auto [x,y] = dq.front();
        dq.pop_front();
        ans = max(ans,depth[x][y]);
        for (auto [dx,dy] : d) {
            int tx = dx + x;
            int ty = dy + y;
            if (inside(tx,ty) and !depth[tx][ty]) {
                if (mat[x][y] == mat[tx][ty]) {
                    depth[tx][ty] = depth[x][y];
                    dq.push_front({tx,ty});
                } else {
                    depth[tx][ty] = depth[x][y] + 1;
                    dq.push_back({tx,ty});
                }
            }
        }
    }

    fout << ans;

    return 0;
}

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