Submission #877966

#	Time	Username	Problem	Language	Result	Execution time	Memory
877966		tigar	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	4027 ms	1048576 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int w, h;
char snow[4001][4001];
int check[4001][4001];
map<pair<int, int>, bool>ch;
vector<int>graff[4040];
queue<int>q;
int ans=0;
bool checkk[4040];
int dist[4040];

void dfs(int x, int y, int br)
{
    if(check[x][y]!=0){return;}
    check[x][y]=br;
    int k;
    if(x-1>0)
    {
        if(snow[x-1][y]==snow[x][y])dfs(x-1, y, br);
        else if(snow[x-1][y]!='.')
        {
            if(!ch[{check[x-1][y], br}] and check[x-1][y]!=0)
            {
                ch[{check[x-1][y], br}]=true;
                graff[check[x-1][y]].push_back(br);
                graff[br].push_back(check[x-1][y]);
            }
        }
    }
    if(x+1<=h)
    {
        if(snow[x][y]==snow[x+1][y])dfs(x+1, y, br);
        else if(snow[x+1][y]!='.')
        {
            if(!ch[{check[x+1][y], br}] and check[x+1][y]!=0)
            {
                ch[{check[x+1][y], br}]=true;
                graff[check[x+1][y]].push_back(br);
                graff[br].push_back(check[x+1][y]);
            }
        }
    }
    if(y-1>0)
    {
        if(snow[x][y]==snow[x][y-1])dfs(x, y-1, br);
        else if(snow[x][y-1]!='.')
        {
            if(!ch[{check[x][y-1], br}] and check[x][y-1]!=0)
            {
                ch[{check[x][y-1], br}]=true;
                graff[check[x][y-1]].push_back(br);
                graff[br].push_back(check[x][y-1]);
            }
        }
    }
    if(y+1<=w)
    {
        if(snow[x][y]==snow[x][y+1])dfs(x, y+1, br);
        else if(snow[x][y+1]!='.')
        {
            if(!ch[{check[x][y+1], br}] and check[x][y+1]!=0)
            {
                ch[{check[x][y+1], br}]=true;
                graff[check[x][y+1]].push_back(br);
                graff[br].push_back(check[x][y+1]);
            }
        }
    }
    return;
}

void bfs(int v)
{
    if(q.empty())return;
    q.pop();
    for(int i=0; i<graff[v].size(); i++)
    {
        if(!checkk[graff[v][i]])
        {
            checkk[graff[v][i]]=true;
            q.push(graff[v][i]);
            dist[graff[v][i]]=dist[v]+1;
            ans=max(ans, dist[graff[v][i]]);
        }
    }
    int ad=q.front();
    bfs(ad);
    return;
}

int main()
{
    cin>>h>>w;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)cin>>snow[i][j];
    }
    int brr=1;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)
        {
            if(snow[i][j]=='.')check[i][j]=true;
            else if(!check[i][j]){dfs(i, j, brr); brr++;}
        }
    }
    q.push(1);
    bfs(1);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void dfs(int, int, int)':
tracks.cpp:19:9: warning: unused variable 'k' [-Wunused-variable]
   19 |     int k;
      |         ^
tracks.cpp: In function 'void bfs(int)':
tracks.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0; i<graff[v].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~

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