QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799830#1453. Froggerhos.lyric🐇#AC ✓171ms39428kbC++142.6kb2024-12-05 18:34:022024-12-05 18:34:03

Judging History

This is the latest submission verdict.

  • [2024-12-05 18:34:03]
  • Judged
  • Verdict: AC
  • Time: 171ms
  • Memory: 39428kb
  • [2024-12-05 18:34:02]
  • Submitted

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'