Submission #895600

#	Time	Username	Problem	Language	Result	Execution time	Memory
895600		dpsaveslives	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	506 ms	121952 KiB

tracks

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 4010;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int H,W; cin >> H >> W;
    for(int i = 1;i<=H;++i){
        for(int j = 1;j<=W;++j){
            cin >> grid[i][j];
        }
    }
    int ans = 0;
    int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
    dist[1][1] = 1;
    deque<pair<int,int>> q; q.push_back({1,1});
    while(!q.empty()){
        int r = q.front().f, c = q.front().s; q.pop_front();
        ans = max(ans,dist[r][c]);
        //cout << r << " " << c << " " << dist[r][c] << "\n";
        for(int i = 0;i<4;++i){
            int nr = r+dx[i], nc = c+dy[i];
            if(nr < 1 || nc < 1 || nr > H || nc > W) continue;
            if(dist[nr][nc] == 0){
                if(grid[nr][nc] == '.') continue;
                if(grid[r][c] != grid[nr][nc]){
                    q.push_back({nr,nc});
                    dist[nr][nc] = dist[r][c]+1;
                }
                else{
                    q.push_front({nr,nc});
                    dist[nr][nc] = dist[r][c];
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

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