#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;
const int N = 2e3 + 50;
int steps[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
set <pair <int, pii> > q;
int n, m, sx, sy, ex, ey;
int nm[300];
int d[N][N];
char c[N][N];
void go(int x, int y, int cnt, int i) {
if (i == 4) {
return;
}
int cx = x + steps[i][0];
int cy = y + steps[i][1];
if (cx < 1 || cy < 1 || cx > n || cy > m || d[cx][cy] <= cnt) {
return;
}
d[cx][cy] = cnt;
q.insert({cnt, {cx, cy}});
}
void change(int x, int y, int cnt) {
for (int i = 0; i < 4; i++) {
go(x, y, cnt + 1, i);
}
}
void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] = 1e9;
}
}
d[sx][sy] = 0;
q.insert({0, {sx, sy}});
while (sz(q)) {
int x = (*q.begin()).S.F;
int y = (*q.begin()).S.S;
int cnt = (*q.begin()).F;
q.erase(q.begin());
if (x == ex && y == ey) {
break;
}
go(x, y, cnt, nm[c[x][y]]);
change(x, y, cnt);
}
}
int main()
{
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("toys.in");
// out("toys.out");
// in("input.txt");
// out("output.txt");
// cerr.precision(9); cerr << fixed;
// clock_t tStart = clock();
cin >> n >> m;
nm['<'] = 0; nm['>'] = 1; nm['v'] = 2; nm['^'] = 3; nm['.'] = 4;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
if (c[i][j] == 'o') {
sx = i;
sy = j;
}
if (c[i][j] == 'x') {
ex = i;
ey = j;
}
}
}
solve();
cout << d[ex][ey] << el;
}
/*
7
4 6 7 2 3 1 5
*/
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:85:32: warning: array subscript has type 'char' [-Wchar-subscripts]
85 | go(x, y, cnt, nm[c[x][y]]);
| ~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
