제출 #444368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444368		mhsi2005	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1491 ms	127116 KiB

tracks

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

const int maxn = 4000 + 10, INF = 1e9 + 10;

int n, m, h, w, d[maxn][maxn], mx;
bool vis[maxn];
char meadow[maxn][maxn];

int main() {
    memset(d, INF, sizeof(d));
    cin >> h >> w;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            cin >> meadow[i][j];
    int adjx[4]{1, -1, 0, 0}, adjy[4]{0, 0, 1, -1};
    d[1][1] = 0;
    deque<pair<int, int>> q;
    q.push_back({1, 1});
    while (q.size()) {
        auto v = q.front();
        q.pop_front();
        for (int i = 0; i < 4; i++) {
            int x = v.first + adjx[i],
                y = v.second + adjy[i];
            if (x < 1 || y < 1 || x > h || y > w || meadow[x][y] == '.') continue;
            int w = !(meadow[v.first][v.second] == meadow[x][y]);
            if (d[v.first][v.second] + w < d[x][y]) {
                d[x][y] = d[v.first][v.second] + w;
                mx = max(mx, d[x][y]);
                if (w == 1)
                    q.push_back({x, y});
                else
                    q.push_front({x, y});
            }
        }
    }
    cout << mx + 1 << '\n';
    return 0;
}

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