Submission #1277872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277872		kiteyu	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	563 ms	143368 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4000;
const int inf = 1e9;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};

struct node{
    int x,y,w;
};
int n, m;
char a[N+5][N+5];
int d[N+5][N+5];

bool chk(int x,int y){
    return (1 <= x && x <= n && 1 <= y && y <= m && a[x][y] != '.');
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j){
            cin >> a[i][j];
            d[i][j] = inf;
        }

    deque<node> Deque;
    Deque.push_back({1,1,1});
    d[1][1] = 1;
    while(!Deque.empty()){
        node t = Deque.front();
        Deque.pop_front();
        int x = t.x;
        int y = t.y;
        int w = t.w;
        if(w > d[x][y]) continue;
        //cout << x <<' ' << y << ' ' <<w << '\n';
        for(int j = 0 ; j < 4 ; ++j){
            int _x = x + dx[j];
            int _y = y + dy[j];
            if(!chk(_x,_y)) continue;
            int _w = w + (a[_x][_y] != a[x][y]);
            //cout << _x << '.' << _y <<' ' <<_w << '\n';
            if(_w < d[_x][_y]){
                d[_x][_y] = _w;
                if(_w > w) Deque.push_back({_x,_y,_w});
                else Deque.push_front({_x,_y,w});
            }
        }
    }
    int mx = 0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(a[i][j] != '.')
            mx = max(mx,d[i][j]);
    cout << mx;
    return 0;
}

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