Submission #533956

#TimeUsernameProblemLanguageResultExecution timeMemory
533956AbrahamJTracks in the Snow (BOI13_tracks)C++98
100 / 100
922 ms159016 KiB
    #include<iostream>
    #include<deque>
    #include<utility>
    using namespace std;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    char t[4010][4010];
    bool odw[4010][4010];
    int ile[4010][4010];
    int main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>t[i][j];
        deque<pair<int,pair<int,int> > > kolejka;
        kolejka.push_front({-1,{1,1}});
        odw[1][1]=1;
        int wynik=0;
        while(!kolejka.empty())
        {
            pair<int,pair<int,int> > para=kolejka.front();
            kolejka.pop_front();
            for(int i=0;i<4;i++)
            {
                int nowy_x=dx[i]+para.second.first;
                int nowy_y=dy[i]+para.second.second;
                if(nowy_x<1 || nowy_x>n || nowy_y<1 || nowy_y>m)
                    continue;
                if(t[nowy_x][nowy_y]=='.')
                    continue;
                if(odw[nowy_x][nowy_y]==0)
                {
                    odw[nowy_x][nowy_y]=1;
                    if(t[nowy_x][nowy_y]==t[para.second.first][para.second.second])
                    {
                        kolejka.push_front({para.first,{nowy_x,nowy_y}});
                        ile[nowy_x][nowy_y]=-para.first;
                    }
                    else {
                        kolejka.push_back({para.first-1,{nowy_x,nowy_y}});
                        ile[nowy_x][nowy_y]=-para.first+1;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                wynik=max(wynik,ile[i][j]);
        cout<<wynik;
        return 0;
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...