| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 646213 | Baytoro | 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 Baytoro_MayrambekovOrz void solve()
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
const int INF=1e18;
void fopn(string name){
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int binpow(int a,int n){
if(n==0)
return 1;
if(n%2==1)
return binpow(a, n-1)*a;
else{
int b=binpow(a, n/2);
return b*b;
}
}
char ar[2005][2005];
int dist[2005][2005];
vector<pair<int,int>> d = {
{0,1},
{0,-1},
{1,0},
{-1,0}
};
int n,m;
int cnt;
int h,g,c,q,r,i,j,k,x,y,res=0;
Baytoro_MayrambekovOrz{
cin>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>ar[i][j];
}
}
res=1;
deque<pair<int,int>> dq;
dq.push_front({1,1});
dist[1][1]=1;
while(!dq.empty()){
auto a=dq.front();
dq.pop_front();
res=max(res,dist[a.fr][a.sc]);
for(i=0;i<4;i++){
int tx=a.fr+d[i].fr;
int ty=a.sc+d[i].sc;
if(tx>0 && ty>0 && tx<=n && ty<=m && dist[tx][ty]==0 && ar[tx][ty]!='.'){
if(ar[a.fr][a.sc]==ar[tx][ty]){
dist[tx][ty]=dist[a.fr][a.sc];
dq.push_front({tx,ty});
}
else{
dist[tx][ty]=dist[a.fr][a.sc]+1;
dq.push_back({tx,ty});
}
}
}
}
cout<<res<<endl;
}
main(){
//fopn("tractor");#include <bits/stdc++.h>
using namespace std;
#define Baytoro_MayrambekovOrz void solve()
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
const int INF=1e18;
void fopn(string name){
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int binpow(int a,int n){
if(n==0)
return 1;
if(n%2==1)
return binpow(a, n-1)*a;
else{
int b=binpow(a, n/2);
return b*b;
}
}
char ar[4005][4005];
int dist[4005][4005];
vector<pair<int,int>> d = {
{0,1},
{0,-1},
{1,0},
{-1,0}
};
int n,m;
int cnt;
int h,g,c,q,r,i,j,k,x,y,res=0;
Baytoro_MayrambekovOrz{
cin>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>ar[i][j];
}
}
res=1;
deque<pair<int,int>> dq;
dq.push_front({1,1});
dist[1][1]=1;
while(!dq.empty()){
auto a=dq.front();
dq.pop_front();
res=max(res,dist[a.fr][a.sc]);
for(i=0;i<4;i++){
int tx=a.fr+d[i].fr;
int ty=a.sc+d[i].sc;
if(tx>0 && ty>0 && tx<=n && ty<=m && dist[tx][ty]==0 && ar[tx][ty]!='.'){
if(ar[a.fr][a.sc]==ar[tx][ty]){
dist[tx][ty]=dist[a.fr][a.sc];
dq.push_front({tx,ty});
}
else{
dist[tx][ty]=dist[a.fr][a.sc]+1;
dq.push_back({tx,ty});
}
}
}
}
cout<<res<<endl;
}
main(){
//fopn("tractor");
//ios;
int T=1;
//cin>>T;
while(T--){
solve();
}
}
//ios;
int T=1;
//cin>>T;
while(T--){
solve();
}
}