Submission #794238

#	Time	Username	Problem	Language	Result	Execution time	Memory
794238		hanlei35	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1006 ms	130844 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

char grid[4000][4000];
int H, W, dist[4000][4000];
const int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0}, mx = 1e9;

int main(){
    cin >> H >> W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> grid[i][j];
            
            dist[i][j] = mx;
        }
    }
    
    deque<pair<int,int>> d;
    dist[0][0] = 1;
    d.push_back({0,0});
    int ans = 0;
    
    while(!d.empty()){
        pair<int,int> curr = d.front();
        d.pop_front();
        
        ans = max(ans, dist[curr.first][curr.second]);
        for(int i=0;i<4;i++){
            int x = curr.first + dx[i], y = curr.second + dy[i];
            if(x >= 0 && x < H && y >= 0 && y < W && grid[x][y] != '.'){
                int w = grid[x][y] == grid[curr.first][curr.second] ? 0:1;
                
                if(dist[curr.first][curr.second] + w < dist[x][y]){
                    dist[x][y] = dist[curr.first][curr.second] + w;
                    
                    if(w == 0) d.push_front({x,y});
                    else d.push_back({x,y});
                }
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

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