| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 941204 | dsyz | Maze (JOI23_ho_t3) | 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;
using ll = long long;
#define MAXN (1000005)
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll R,C,N;
cin>>R>>C>>N;
pair<ll,ll> start, end;
cin>>start.first>>start.end;
cin>>end.first>>end.second;
start.first--, start.second--, end.first--, end.second--;
char arr[R][C];
for(ll i = 0;i < R;i++){
for(ll j = 0;j < C;j++){
cin>>arr[i][j];
}
}
queue<pair<ll,ll> > q;
ll dist[R][C][2];
for(ll i = 0;i < R;i++){
for(ll j = 0;j < C;j++){
dist[i][0] = 1e18;
dist[i][1] = 1e18;
}
}
q.push({start.first,start.end});
dist[start.first][start.second][0] = 0;
while(!q.empty()){
ll y = q.front().first;
ll x = q.front().second;
q.pop();
for(ll i = -2;i <= 2;i++){
for(ll j = -2;j <= 2;j++){
ll a = y + i;
ll b = x + j;
if(a < 0 || a >= R || b < 0 || b >= C) continue;
if(arr[a][b] == '.'){ //white
if(arr[y][x] == '.'){
dist[y][x][1] = min(dist[y][x][1],1 + min(dist[a][b][0],dist[a][b][1]));
}else{
dist[y][x][1] = min(dist[y][x][1],1 + min(dist[a][b][0],dist[a][b][1]));
dist[y][x][0] = min(dist[y][x][0],min(dist[a][b][0],dist[a][b][1]));
}
}else{ //black
if(arr[y][x] == '.'){
dist[y][x][1] = min(dist[y][x][1],1 + dist[a][b][1]);
}else{
dist[y][x][1] = min(dist[y][x][1],1 + dist[a][b][1]);
dist[y][x][0] = min(dist[y][x][0],dist[a][b][1]);
}
}
}
}
}
}