Submission #1101435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101435		abel2008	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	2857 ms	1048580 KiB

tracks

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
int n,m,cnt = 0,di[4] = {-1,0,1,0},dj[4] = {0,1,0,-1},maxx = 0;
bool adj[4003][4003];
bool viz[4003][4003];
int viz1[4003*4003];
char ma[4003][4003];

bool inside(int x,int y) {
        return x>=1&&x<=n&&y>=1&&y<=m;
}

void dfs(int x,int y,int crt,char ch) {
        viz[x][y] = crt;
        for (int k = 0;k<4;++k) {
                int crtx = x+di[k],crty = y+dj[k];
                if (inside(crtx,crty)&&viz[crtx][crty]==0&&ma[crtx][crty]==ch) {
                        dfs(crtx,crty,crt,ch);
                } else if (inside(crtx,crty)&&viz[crtx][crty]!=0&&ma[crtx][crty]!=ch) {
                        adj[crt][viz[crtx][crty]] = 1;
                        adj[viz[crtx][crty]][crt] = 1;
                }
        }
}

void bfs(int k) {
        viz1[k] = 1;
        queue<int> Q;
        Q.push(k);
        maxx = max(maxx,viz1[k]);
        while(!Q.empty()) {
                int crt = Q.front();
                Q.pop();
                for (int j = 1;j<=m;++j) {
                        if (adj[k][j]) {
                                if (viz1[j]==0) {
                                        viz1[j] = viz1[crt]+1;
                                        Q.push(crt);
                                        maxx = max(maxx,viz1[j]);
                                }
                        }
                }
        }
}


int main() {
        cin>>n>>m;
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=m;++j) {
                        cin>>ma[i][j];
                }
        }
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=m;++j) {
                        if (ma[i][j]!='.'&&viz[i][j]==0) {
                                dfs(i,j,++cnt,ma[i][j]);
                        }
                }
        }
        bfs(1);
        cout<<maxx<<endl;
        return 0;
}

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