Submission #749154

#	Time	Username	Problem	Language	Result	Execution time	Memory
749154		farica	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	761 ms	126736 KiB

tracks

#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1e9+7;
const int MAX_N = 1e6;
const int MAX_N2 = 1e5;
const int TWO_MOD_INV = 500000004;
const int M = 998244353;

int depth[4000][4000], dx[4]={1, -1, 0, 0}, h,w, dy[4]={0, 0, 1, -1};
char grid[4000][4000];

bool inside(int x, int y) {
    if(x>=0 && y>=0 && x<h && y<w && grid[x][y]!='.') return 1;
    return 0;
}

void solve() {
    cin >> h >> w;
    for(int i=0; i<h; ++i) {
        string s;
        cin >> s;
        for(int j=0; j<w; ++j) {
            grid[i][j]=s[j];
        }
    }
    deque<pair<int,int>>q;
    q.push_back({0, 0});
    int ans=0;
    memset(depth, 0, sizeof depth);
    depth[0][0]=1;
    while(!q.empty()) {
        pair<int,int>c=q.front();
        q.pop_front();
        ans=max(ans, depth[c.first][c.second]);
        for(int i=0; i<4; ++i) {
            int x=c.first+dx[i], y=c.second+dy[i];
            if(!inside(x,y) or depth[x][y]) continue;
            if(grid[x][y]==grid[c.first][c.second]) {
                depth[x][y]=depth[c.first][c.second];
                q.push_front({x,y});
            } else {
                depth[x][y]=depth[c.first][c.second]+1;
                q.push_back({x, y});
            }
        }
    }
    cout << ans << endl;
}

signed main()
{

    //freopen("odometer.in","r",stdin);
    //freopen("odometer.out","w",stdout);

    int t=1;
    while(t--) solve();

    return 0;
}

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