Submission #436692

#	Time	Username	Problem	Language	Result	Execution time	Memory
436692		alexis_1729	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	871 ms	153144 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
const int maxn=1e4+1;
const int MOD=1e9+7;
int h,w;
char mx[maxn][maxn]; int ca[maxn][maxn];
#define pi pair<int,int>
int vx[]={1, -1, 0, 0},
    vy[]={0, 0, 1, -1};
    bool good(int x,int y){
       return x>=0 && x<h && y>=0 && y<w && mx[x][y]!='.';

    }
 int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
      cin>>h>>w;
      for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>mx[i][j];
        }
      }
      deque<pi>dq;
      dq.push_back({0,0});int ans=0;
      ca[0][0]=1;
       while(!dq.empty()){
            pi a=dq.front();
               dq.pop_front();
        ans=max(ans,ca[a.first][a.second]);

        for(int i=0;i<4;i++){
                int x,y;
              x=a.first+vx[i];y=a.second+vy[i];
               if(good(x,y) &&  ca[x][y]==0){
                         if(mx[x][y]==mx[a.first][a.second]){
                                ca[x][y]=ca[a.first][a.second];
                                dq.push_front({x,y});
                         }else{
                               ca[x][y]=ca[a.first][a.second]+1;
                               dq.push_back({x,y});
                         }
                     }
                  }
              }
    cout<<ans;
}

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