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<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define int long long
#define len(x) (int)x.size()
#define all(x) (x).begin() , (x).end()
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int , int>
#define F first
#define S second
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
int n , w , h;
char a[505][505];
int dp[15][15][15];
int tmp = 1;
bool used[15][15];
void dfs(int x , int y , int p = 0){
used[x][y] = 1;
if(p != 1){
int y1 = y;
while(y < w and a[x][y + 1] != 'x')y++;
dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x][y1] + 1);
if(!used[x][y])dfs(x , y , 1);
y = y1;
}
if(p != 2){
int y1 = y;
while(y > 1 and a[x][y - 1] != 'x')y--;
dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x][y1] + 1);
if(!used[x][y])dfs(x , y , 2);
y = y1;
}
if(p != 3){
int x1 = x;
while(x > 1 and a[x - 1][y] != 'x')x--;
dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x1][y] + 1);
if(!used[x][y])dfs(x , y , 3);
x = x1;
}
if(p != 4){
int x1 = x;
while(x < h and a[x + 1][y] != 'x')x++;
dp[tmp][x][y] = min(dp[tmp][x][y] , dp[tmp][x1][y] + 1);
if(!used[x][y])dfs(x , y , 4);
x = x1;
}
}
//1 >
//2 <
//3 ^
//4 v
void skibidi_dop_dop_dop_yes_yes(){
cin >> n >> w >> h;
vector<pii> v;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
cin >> a[i][j];
dp[1][i][j] = dp[2][i][j] = inf;
if(a[i][j] >= '1' and a[i][j] <= '9')v.pb({i , j});
}
}
for(auto it : v){
dp[tmp][it.F][it.S] = 0;
dfs(it.F , it.S);
tmp++;
for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)used[i][j] = 0;
}
int mn = inf;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
mn = min(mn , dp[1][i][j] + dp[2][i][j]);
}
}
if(mn < inf)cout << mn;
else cout << -1;
}
signed main(){
int t = 1;
Bekabot
while(t--)skibidi_dop_dop_dop_yes_yes();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |