Submission #1101476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101476		abel2008	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	870 ms	133720 KiB

tracks

#include <iostream>
#include <deque>
#include <utility>
using namespace std;
int n,m,di[4] = {-1,0,1,0},dj[4] = {0,1,0,-1},ans = 0;
char ma[4003][4003];
int viz[4003][4003];

void bfs(int x,int y) {
        viz[x][y] = 1;
        deque<pair<int,int>> dq;
        dq.emplace_front(x,y);
        ans = max(ans,viz[x][y]);
        while(!dq.empty()) {
                pair<int,int> pi = dq.front();
                dq.pop_front();
                int x = pi.first,y = pi.second;
                for (int k = 0;k<4;++k) {
                        int crtx = x+di[k],crty = y+dj[k];
                        if (crtx>=1&&crtx<=n&&crty>=1&&crty<=m&& ma[crtx][crty]!='.'&&viz[crtx][crty]==0) {
                                if (ma[crtx][crty]==ma[x][y]) {
                                        viz[crtx][crty] = viz[x][y];
                                        ans = max(ans,viz[crtx][crty]);
                                        dq.emplace_front(crtx,crty);
                                } else {
                                        dq.emplace_back(crtx,crty);
                                        viz[crtx][crty] = viz[x][y]+1;
                                        ans = max(ans,viz[crtx][crty]);
                                }
                        }
                }
        }
}

int main() {
        cin>>n>>m;
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=m;++j) {
                        cin>>ma[i][j];
                }
        }
        bfs(1,1);
        cout<<ans;
        return 0;
}

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