Submission #1295685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295685		silver_bullet	Tracks in the Snow (BOI13_tracks)	C++20	19.79 / 100	807 ms	119328 KiB

tracks

#include<bits/stdc++.h> 
using namespace std;
const int maxN = (int)4e3 + 2;
const int maxM = (int)4e3 + 2;
char c[maxN][maxM];
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
int dist[maxN][maxM]; 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin >> c[i][j],dist[i][j] = INT_MAX - 10;
    dist[1][1] = 1;
    deque<array<int,2>> dq;
    dq.push_front({1,1}); 
    while(dq.size())
    {
        int x = dq.front()[0];
        int y = dq.front()[1];
        dq.pop_front();
        for(int i=0;i<4;++i)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m) 
            {
                int cost = 0;
                if(c[nx][ny] != c[x][y]) ++cost;
                if(dist[nx][ny] > dist[x][y] + cost)
                {
                    dist[nx][ny] = dist[x][y] + cost;
                    if(!cost) dq.push_front({nx,ny});
                    else dq.push_back({nx,ny}); 
                }
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ans = max(ans,dist[i][j]);
    cout << ans; 
    return 0; 
}

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