QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799830 | #1453. Frogger | hos.lyric🐇# | AC ✓ | 171ms | 39428kb | C++14 | 2.6kb | 2024-12-05 18:34:02 | 2024-12-05 18:34:03 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
int M, N;
char A[60][60];
int mod(int x, int m) {
return ((x %= m) < 0) ? (x + m) : x;
}
int dist[2510][60][60];
int main() {
for (; ~scanf("%d%d", &M, &N); ) {
for (int x = 0; x < M; ++x) {
scanf("%s", A[x]);
}
const int L = M / __gcd(M, N) * N;
queue<pair<int, pair<int, int>>> que;
memset(dist, ~0, sizeof(dist));
dist[0][0][0] = 0;
que.emplace(0, make_pair(0, 0));
for (; que.size(); ) {
const int r = que.front().first;
const int x = que.front().second.first;
const int y = que.front().second.second;
que.pop();
auto visit = [&](int rr, int xx, int yy) -> void {
if (rr >= L) rr -= L;
xx = mod(xx, M);
yy = mod(yy, N);
if (!~dist[rr][xx][yy]) {
dist[rr][xx][yy] = dist[r][x][y] + 1;
que.emplace(rr, make_pair(xx, yy));
}
};
if (A[mod(x - r, M)][y] == 'v') visit(r + 1, x + 1, y);
if (A[mod(x + r, M)][y] == '^') visit(r + 1, x - 1, y);
if (A[x][mod(y - r, N)] == '>') visit(r + 1, x, y + 1);
if (A[x][mod(y + r, N)] == '<') visit(r + 1, x, y - 1);
}
int ans = -1;
for (int r = 0; r < L; ++r) {
const int d = dist[r][M - 1][N - 1];
if (~d) {
if (!~ans || ans > d) ans = d;
}
}
printf("%d\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 39420kb
input:
3 5 >^..v ...<. .v..^
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 3ms
memory: 39112kb
input:
3 5 <.... .v... ...>.
output:
31
result:
ok answer is '31'
Test #3:
score: 0
Accepted
time: 0ms
memory: 39124kb
input:
2 2 >< ><
output:
-1
result:
ok answer is '-1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 39128kb
input:
49 50 <................................................. .v................................................ .................................................. .................................................. .................................................. ..........................................
output:
4946
result:
ok answer is '4946'
Test #5:
score: 0
Accepted
time: 4ms
memory: 39180kb
input:
50 49 <................................................ .v............................................... ................................................. ................................................. ................................................. ...............................................
output:
4945
result:
ok answer is '4945'
Test #6:
score: 0
Accepted
time: 3ms
memory: 39404kb
input:
50 50 <................................................. .v................................................ .................................................. .................................................. .................................................. ..........................................
output:
146
result:
ok answer is '146'
Test #7:
score: 0
Accepted
time: 0ms
memory: 39128kb
input:
47 48 <............................................... .v.............................................. ................................................ ................................................ ................................................ ................................................ ...
output:
4556
result:
ok answer is '4556'
Test #8:
score: 0
Accepted
time: 0ms
memory: 39132kb
input:
2 2 ^. ..
output:
-1
result:
ok answer is '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 39416kb
input:
2 2 ^v ^.
output:
-1
result:
ok answer is '-1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 39120kb
input:
2 2 ^v <v
output:
-1
result:
ok answer is '-1'
Test #11:
score: 0
Accepted
time: 3ms
memory: 39108kb
input:
2 3 v.. ...
output:
-1
result:
ok answer is '-1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 39416kb
input:
2 3 ^<> .^.
output:
-1
result:
ok answer is '-1'
Test #13:
score: 0
Accepted
time: 3ms
memory: 39416kb
input:
2 3 vvv <^<
output:
4
result:
ok answer is '4'
Test #14:
score: 0
Accepted
time: 0ms
memory: 39112kb
input:
4 3 v.. ... ... ...
output:
-1
result:
ok answer is '-1'
Test #15:
score: 0
Accepted
time: 0ms
memory: 39184kb
input:
4 3 v.. <.. >>. .v>
output:
9
result:
ok answer is '9'
Test #16:
score: 0
Accepted
time: 3ms
memory: 39416kb
input:
4 3 vv> v>< <^> <>>
output:
4
result:
ok answer is '4'
Test #17:
score: 0
Accepted
time: 0ms
memory: 39088kb
input:
25 50 >....................................v............ ...............................<.................. ........v......................................... ...........................^...................... .................................................. ..........................................
output:
-1
result:
ok answer is '-1'
Test #18:
score: 0
Accepted
time: 3ms
memory: 39124kb
input:
50 25 v........................ ......................... ...............>......... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ...........
output:
-1
result:
ok answer is '-1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 39068kb
input:
27 50 >..........................^...................... .........................<........................ .................................................. .................................................. ...................................>.............. ..........................................
output:
803
result:
ok answer is '803'
Test #20:
score: 0
Accepted
time: 4ms
memory: 39112kb
input:
50 27 v.......................... ........................... ........................... ........................... .............v............. ......................>.... ........................... ........................... ..........^................ ........................... .................
output:
-1
result:
ok answer is '-1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 39412kb
input:
50 50 ^................................................. ....................................v............. .................................................. .................................................> .................................................. ..........................................
output:
-1
result:
ok answer is '-1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 39092kb
input:
49 50 >................................................. ..................................^............... .................................................. ..........<....................................... ..........................^....................... ..........................................
output:
-1
result:
ok answer is '-1'
Test #23:
score: 0
Accepted
time: 7ms
memory: 39132kb
input:
25 50 ^........<..<.....<..>.......>.........v.......... .......^................<<........................ ....^..<v.>...................v....v.............. .....<.......>.......<......v..................... .......v............................v.>........... .........v.................>^.....v.......
output:
86
result:
ok answer is '86'
Test #24:
score: 0
Accepted
time: 0ms
memory: 39124kb
input:
50 25 ^.................v...... ................>..v..... .v....v........<......... ...^.....>..><.....>...^v ...............>v.<...... ...v...................>. ......................... .............v........... ..^....<..^.............. .<...v................... .....v.........^.^..v.... .....^.....
output:
77
result:
ok answer is '77'
Test #25:
score: 0
Accepted
time: 8ms
memory: 39116kb
input:
27 50 v.......^.>..>.<...>.....v..........<........v.... ..............>v.................v................ .v..<v............................^............... .................<.......^......>..........<...... ...^...v............................>........v>... ............>.v.....>.....................
output:
50
result:
ok answer is '50'
Test #26:
score: 0
Accepted
time: 8ms
memory: 39416kb
input:
50 27 <.v.....<....>^....<>...... >..^<........>...^.....^v.. ........^....<<............ .<...>......^.............. ......^.................... .........v.>>.............. ......v.............v....>. ..........................> ......>...............v.... .......................^... ....v...<........
output:
94
result:
ok answer is '94'
Test #27:
score: 0
Accepted
time: 0ms
memory: 39112kb
input:
50 50 ^..........>^............<............<.......^... .....<.......>.v........................<........> .................>................................ ........................................>......... .....>....>.......<...........v.....v<...v....^... >....................<..............^.....
output:
-1
result:
ok answer is '-1'
Test #28:
score: 0
Accepted
time: 15ms
memory: 39188kb
input:
49 50 <.........^..................>...........^........ .....................v........................>... .......<.>.>............>v........................ .v.v...<...........................>.<......^..... .........<.......>...................>............ .......................v...........v......
output:
210
result:
ok answer is '210'
Test #29:
score: 0
Accepted
time: 0ms
memory: 39096kb
input:
25 50 >v.<v.^vv.>..v..v<v>.><v......v.^..>>.v<..v>>><.^< ^.^^..^^>..^.>^..^^...v^^>..v^v.>.<>.<><><.<>.>.^. <...>>v.<v.>^.>>v^.v...><.<>^^<v>^.>v..>>.>v>v.... vv><>.^<.>v..>.v>..>.^<.v<.>.<v<vv><^.vv..^.^.<^.. <.>v.>.^<.v^v.<.v^^<v..v.>v.vv^>^<><^>>..>..>^><^. .v>^^<.v.^^>.^>vvv...<.>...<>>><.<<.>>....
output:
20
result:
ok answer is '20'
Test #30:
score: 0
Accepted
time: 0ms
memory: 39372kb
input:
50 25 <^^^.v<^>...^v<^<v..^v<<^ .^<<<..>><.<v.^...>.<vvv< >.<^.v.^.^<v.^.^><^.^><^. ^.>.^^<vv.^<<.<><<^....^v .....>.<^<.<>v.v.v...<^<. >.v>.v<<^..^<>v>>.<..^^>. vv><^^..^^^.<^>.<.<<v.v>> .><>.v^v>.^.>.^.^>^<.v>>< .>.>^vv.>^v..>....v><>><. .>....v>.<.v>^.<.<^^>.v.. .^v..v>..<v.^><v<v.>.<..> v><.^......
output:
12
result:
ok answer is '12'
Test #31:
score: 0
Accepted
time: 35ms
memory: 39076kb
input:
27 50 ^>^..<.^.^<.<^v<v.><v^<.v.^.v.^.v>v^>>.v.vv..^<.<v .<>>....><v^^.^.v..^.^>..v>.v.>.vv<.^..^^v<.....v. vv^<.<<<^.<v.<<.v.v...^^^<.>.v..v.^.v<^<>.^vvv^><< ^..><><..<>>v.^><v>..<v..<.<v^<>..vv>..>vv.>^v.^<. vvv.^...vvv..<.v<<..<.^...><<.<v...<vv...v..>...v. .><<.^vv><v...><....>.>v>.^>.>.^v<.>.^^...
output:
2
result:
ok answer is '2'
Test #32:
score: 0
Accepted
time: 34ms
memory: 39144kb
input:
50 27 ><^<>>...v^.<>.<><<^.>^.<.. v..v^^>.^.>..^^.^.>^v^^><.< ^<>>.v^.^v.>.^.....^..^.>^v ^.<v.^^.>>..v..<>^.vvv>.<.. ...<>v..<v.v.vv>.v^^<.v<<.^ ..v.>.^>.>^>...^v...<..<<^. >.v^...^...<v^^<.^>...<^<.< .^.v>.^<^.v..>v^<^v^.>.^^.^ ^<..<v^.<.vv.v<.<^>^...^.<^ >vv..><^.v^><.<...>.<..^v.> .v<.vv<^v..>.^...
output:
22
result:
ok answer is '22'
Test #33:
score: 0
Accepted
time: 0ms
memory: 39188kb
input:
50 50 ^>..^..>^^....<>^.<..><v.v....v>..<..^.v.<.vv^v... ^>^>v<<^^<.....v.v.^><^><.v^..>>.^>.^...^.v^.<<... >.^<<.>v...>^>>>.v>.><<.>v..v.><<<.>v^.^..>..^.>.^ ..><.>v>...>v.>vv.<<^^..>.<<<>^^v.^.>v^v<^....v^>^ <<>v<^>^.<>v..>....<....>.<^.<>>vv...^.<^^<>>>^v^> <<v....^<>>..v..v^..^^<.^v>..v^..>.<^<^...
output:
16
result:
ok answer is '16'
Test #34:
score: 0
Accepted
time: 113ms
memory: 39428kb
input:
49 50 vv<..v.>v>...<.......^>v..v.>>.><.v>v<>vv<>v.^v.^v ^^><^>^.v<>v<<>....v.^.v..^.v.><^.v^<v.<..>.v.<..< .>...>v<.v<<>^<.>^<.v^>.>>.>^<<v^..^v.<>.<v^..v.<> ..v^<..^vvv<^v^..v^><v.vv.<v^<<..v..<v<..v<.v.<><< >^.^>>.v.v....^..^>..>..<..v..^v^..^><v^^<<.<^.<.. .>v.v^^.^.^^v<^..v^^<>^<..^>^..>vv.^<^....
output:
16
result:
ok answer is '16'
Test #35:
score: 0
Accepted
time: 0ms
memory: 39428kb
input:
50 50 ^<^><>^^>>vv^>>><^v<v<><>^<v<>v>v^^<>^^v^v>v^^^^>v <^v><^^<v^^^<>>^<><^^^^^v<<v<vvvv^^^<><v>>v>v>^^^> <>^^<><^>v<^><<>^^>v<v<<>v^<^>>^vv<v>>><v>v<<v^>>< v<v<>vv>^<v^<<>>^><vv<v^<v<^^>>v<v><v><^^v<v<<^v^< >><v>^>^>>^>><v<<v<v^<v>^^<^v>^^^><^^^^>v<>>^<^>v> >v<><v<^<^><<><<<^<^<^><<>v>v^<>v<<<<v>...
output:
2
result:
ok answer is '2'
Test #36:
score: 0
Accepted
time: 171ms
memory: 39156kb
input:
49 50 >>><><v<^><^<^^<v<^<^<>^v>^^^v>><^^v^^v<>^><><^><v ^<<^>v><<><vv<vv^vvvv><^<<^<^>vv<>^vv^>^<^v<<>>>>< v^>^<v^^^vv^^^v>>^^^>vv<v>>>^vv>^>^<v<^^^v>v>^^>>^ >v<<>^><<v^vv<v^v>>>^vvv>>vv^vv^<^^v><>>>>^<v^<^<> <^^v^<>^^^v<<^^v<vv^v^^<<<>>>^^v^>vvv>v<^^^v^^^^v> v<<>><<^>^^<^v>>><>vv^v^vv<^>^><<^<<>>>...
output:
10
result:
ok answer is '10'