# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
742282 | irmuun | Tracks in the Snow (BOI13_tracks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int h,w;
cin>>h>>w;
string s[h+5];
int used[h+5][w+5];
memset(used,0,sizeof(used));
int cnt=0;
for(int i=0;i<h;i++){
cin>>s[i];
}
set<pair<int,pair<int,int>>>st;
st.insert({1,{0,0}});
used[0][0]=1;
queue<pair<int,int>>q[h*w+5];
q[1].push({0,0});
for(int i=1;i<=h*w+1;i++){
if(q[i].size()==0){
cout<<i-1
return 0;
}
while(!q[i].empty()){
int x=q[i].front().ff,y=q[i].front().ss;
q[i].pop();
if(x>0&&used[x-1][y]==0){
if(s[x-1][y]==s[x][y]){
used[x-1][y]=1;
q[i].push({x-1,y});
}
else if(s[x-1][y]!='.'){
used[x-1][y]=1;
q[i+1].push({x-1,y});
}
}
if(x<h-1&&used[x+1][y]==0){
if(s[x+1][y]==s[x][y]){
used[x+1][y]=1;
q[i].push({x+1,y});
}
else if(s[x+1][y]!='.'){
used[x+1][y]=1;
q[i+1].push({x+1,y});
}
}
if(y>0&&used[x][y-1]==0){
if(s[x][y-1]==s[x][y]){
used[x][y-1]=1;
q[i].push({x,y-1});
}
else if(s[x][y-1]!='.'){
used[x][y-1]=1;
q[i+1].push({x,y-1});
}
}
if(y<w-1&&used[x][y+1]==0){
if(s[x][y+1]==s[x][y]){
used[x][y+1]=1;
q[i].push({x,y+1});
}
else if(s[x][y+1]!='.'){
used[x][y+1]=1;
q[i+1].push({x,y+1});
}
}
}
}
}