Submission #153755

#	Time	Username	Problem	Language	Result	Execution time	Memory
153755		brcode	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1733 ms	129660 KiB

tracks

#include <iostream>
#include <queue>
using namespace std;
int n,m;
const int MAXN = 4010;
int dx[5] = {1,0,-1,0};
int dy[5] = {0,1,0,-1};
string arr[MAXN];
int dp[MAXN][MAXN];
int ans;
bool check(int x,int y){
    if(x>0 && x<=n && y>0 && y<=m && arr[x][y]!='.'){
        return true;
    }
    return false;
}
 deque<pair<int,int>> q1;
int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i] = '.'+arr[i];
        //cout<<arr[i]<<endl;
    }
   
    dp[1][1] = 1;
  
    q1.push_front(make_pair(1,1));
   
    while(!q1.empty()){
        
        auto curr = q1.front();
        q1.pop_front();
       
        ans = max(ans,dp[curr.first][curr.second]);
        for(int i=0;i<4;i++){
            int x = curr.first+dx[i];
            int y = curr.second+dy[i];
            if(check(x,y) && dp[x][y]==0){
                if(arr[x][y] == arr[curr.first][curr.second]){
                    q1.push_front(make_pair(x,y));
                    dp[x][y] = dp[curr.first][curr.second];
                }else{
                    q1.push_back(make_pair(x,y));
                    dp[x][y] = dp[curr.first][curr.second]+1;
                    
                }
            }
        }
    }
    cout<<ans<<endl;
    
}

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