//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*TAAK ZDES NADO RECURSIU PISAT*/
//MADE BY CHATGPT ANAU MNAU I CHUT CHUT TIMA
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define nep next_permutation
#define itn int
#define reutrn return
#define reutnr return
#define pii pair<int,int>
#define tpii pair<pair<int,int>,int>
#define fpii pair<pair<int,int>,pair<int,int>>
#define sigma signed
#define cni cin
#define cotu cout
#define cotninue continue
#define breka break
#define al(x , y , z) x + z , x + y + z
#define bits(x) __builtin_popcount(x)
using namespace std;
using namespace __gnu_pbds;
const int N = 3e5 + 5;
int mod = 1e9 + 7;
const int modik = 998244353;
const int INF = 1e18;
int n,h,w;
char a[501][501];
map <pii , vector <pii>> g;
map <pii , int> used , dist;
void Tima(){
cin >> n >> h >> w;
pii b , e;
for(int i = 1 ; i <= w ; i++){
for(int j = 1 ; j <= h ; j++){
cin >> a[i][j];
if(a[i][j] == '1'){
b = {i , j};
}
if(a[i][j] == '2'){
e = {i , j};
}
}
}
for(int i = 1 ; i <= w ; i++){
for(int j = 1 ; j <= h ; j++){
if(a[i][j] == 'x') continue;
bool ok = 0;
for(int k = i - 1 ; k >= 1 ; k--){
if(a[k][j] == 'x'){
ok = 1;
g[{i , j}].pb({k + 1 , j});
// g[{k + 1 , j}].pb({i , j});
break;
}
// if(a[k][j] == '1' || a[k][j] == '2'){
// g[{i , j}].pb({k , j});
// }
}
if(!ok){
g[{i , j}].pb({1 , j});
// g[{1 , j}].pb({i , j});
}
ok = 0;
for(int k = i + 1 ; k <= w ; k++){
if(a[k][j] == 'x'){
ok = 1;
g[{i , j}].pb({k - 1 , j});
// g[{k - 1 , j}].pb({i , j});
break;
}
// if(a[k][j] == '1' || a[k][j] == '2'){
// g[{i , j}].pb({k , j});
// }
}
if(!ok){
g[{i , j}].pb({w , j});
// g[{w , j}].pb({i , j});
}
ok = 0;
for(int k = j - 1 ; k >= 1 ; k--){
if(a[i][k] == 'x'){
ok = 1;
g[{i , j}].pb({i , k + 1});
// g[{i , k + 1}].pb({i , j});
break;
}
// if(a[i][k] == '1' || a[i][k] == '2'){
// g[{i , j}].pb({i , k});
// }
}
if(!ok){
g[{i , j}].pb({i , 1});
// g[{i , 1}].pb({i , j});
}
ok = 0;
for(int k = j + 1 ; k <= h ; k++){
if(a[i][k] == 'x'){
ok = 1;
g[{i , j}].pb({i , k - 1});
// g[{i , k - 1}].pb({i , j});
break;
}
// if(a[i][k] == '1' || a[i][k] == '2'){
// g[{i , j}].pb({i , k});
// }
}
if(!ok){
g[{i , j}].pb({i , h});
// g[{i , h].pb({i , j});
}
}
}
deque <pii> q;
for(int i = 1 ; i <= w ; i++){
for(int j = 1 ; j <= h ; j++){
dist[{i , j}] = INF;
}
}
q.pb(b);
used[b] = 1;
dist[b] = 0;
int ans = INF;
while(q.size()){
pii v = q.front();
q.pop_front();
for(auto to : g[v]){
if(!used[to]){
dist[to] = min(dist[v] + 1 , dist[to]);
// cout << v.F << ' ' << v.S << ' ' << to.F << ' ' << to.S << ' ' << a[v.F][v.S] << ' ' << a[to.F][to.S] << ' ' << dist[v] << ' ' << dist[to] << '\n';
used[to] = 1;
q.pb(to);
}
}
}
ans = min(ans , dist[e]);
for(int i = 1 ; i <= w ; i++){
for(int j = 1 ; j <= h ; j++){
dist[{i , j}] = INF;
used[{i , j}] = 0;
}
}
swap(b , e);
q.pb(b);
used[b] = 1;
dist[b] = 0;
// ans = INF;
while(q.size()){
pii v = q.front();
q.pop_front();
for(auto to : g[v]){
if(!used[to]){
// cout << v.F << ' ' << v.S << ' ' << to.F << ' ' << to.S << ' ' << a[v.F][v.S] << ' ' << a[to.F][to.S] << '\n';
dist[to] = min(dist[v] + 1 , dist[to]);
used[to] = 1;
q.pb(to);
}
}
}
ans = min(ans , dist[e]);
cout << (ans == INF ? -1 : ans);
}
//It is not important to be better than someone else, but to be better than you were yesterday...
//Push yourself, because no one else is going to do it for you..
sigma main(){
//freopen("txt.in","r",stdin);
//freopen("txt.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int TT = 1;
// cin >> TT;
for(int i = 1 ; i <= TT ; i++){
//cout << "Case " << i << ": ";
Tima();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
