Submission #380943

#	Time	Username	Problem	Language	Result	Execution time	Memory
380943		zorz	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	875 ms	139216 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define MOD 1000000007
#define vi vector<int>
#define pi pair<int, int>
char g[4005][4005];
int dist[4005][4005]; 
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
int h, w, ans = 1;
int main()
{
    //freopen("13_tracks.in", "r", stdin); 
    //freopen("13_tracks.out", "w", stdout); 
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> h >> w;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            cin >> g[i][j]; 
    deque<pi> q;
    q.push_front({1, 1}); 
    memset(dist, 0x3f, sizeof(dist));
    //cout << dist[1][2] << endl; 
    dist[1][1] = 1;
    while (!q.empty())
    {
        pi t = q.front(); q.pop_front(); 
        int tx = t.first, ty = t.second; 
        ans = max(ans, dist[tx][ty]); 
        for (int i = 0; i < 4; ++i)
        {
            int x = tx + dx[i], y = ty + dy[i]; 
            if (x < 1 || x > h || y < 1 || y > w || g[x][y] == '.') continue; 
            if (dist[x][y] > dist[tx][ty] + (g[x][y] != g[tx][ty]))
            {
                dist[x][y] = dist[tx][ty] + (g[x][y] != g[tx][ty]); 
                if (g[x][y] == g[tx][ty])
                    q.push_front({x, y}); 
                else q.push_back({x, y}); 
            }
        }        
    }
    /*
    for (int i = 1; i <= h; ++i)
    {
        for (int j = 1; j <= w; ++j)
            cout << dist[i][j] << " ";
        cout << endl;
    }        
    */
    cout << ans << endl;
    return 0;
}

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