QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#14898#1453. FroggerQingyuAC ✓205ms3760kbC++201.2kb2021-10-25 12:44:012022-05-17 01:13:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-17 01:13:50]
  • 评测
  • 测评结果:AC
  • 用时:205ms
  • 内存:3760kb
  • [2021-10-25 12:44:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int r,c;
    cin>>r>>c;
    vector<string> grid(r);
    rep(i,0,r) cin>>grid[i];

    auto at = [&](int x, int y) {
        x = (x%r + r) % r;
        y = (y%c + c) % c;
        return grid[x][y];
    };

    vector<vector<vi>> where(2, vector<vi>(r, vi(c,-1)));
    where[0][0][0] = 0;
    rep(i,0,10*r*c) {
        auto& now = where[i%2];
        auto& nxt = where[(i+1)%2];
        if(now[r-1][c-1] >= i) {
            cout << i << endl;
            exit(0);
        }
        rep(x,0,r) rep(y,0,c) if(now[x][y] >= i) {
            if(at(x-i,y) == 'v') nxt[(x+1)%r][y] = i+1;
            if(at(x+i,y) == '^') nxt[(x+r-1)%r][y] = i+1;
            if(at(x,y-i) == '>') nxt[x][(y+1)%c] = i+1;
            if(at(x,y+i) == '<') nxt[x][(y+c-1)%c] = i+1;
        }
    }
    cout << "-1" << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3652kb

input:

3 5
>^..v
...<.
.v..^

output:

5

result:

ok answer is '5'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

3 5
<....
.v...
...>.

output:

31

result:

ok answer is '31'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

2 2
><
><

output:

-1

result:

ok answer is '-1'

Test #4:

score: 0
Accepted
time: 11ms
memory: 3552kb

input:

49 50
<.................................................
.v................................................
..................................................
..................................................
..................................................
..........................................

output:

4946

result:

ok answer is '4946'

Test #5:

score: 0
Accepted
time: 11ms
memory: 3596kb

input:

50 49
<................................................
.v...............................................
.................................................
.................................................
.................................................
...............................................

output:

4945

result:

ok answer is '4945'

Test #6:

score: 0
Accepted
time: 3ms
memory: 3760kb

input:

50 50
<.................................................
.v................................................
..................................................
..................................................
..................................................
..........................................

output:

146

result:

ok answer is '146'

Test #7:

score: 0
Accepted
time: 12ms
memory: 3576kb

input:

47 48
<...............................................
.v..............................................
................................................
................................................
................................................
................................................
...

output:

4556

result:

ok answer is '4556'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

2 2
^.
..

output:

-1

result:

ok answer is '-1'

Test #9:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

2 2
^v
^.

output:

-1

result:

ok answer is '-1'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3636kb

input:

2 2
^v
<v

output:

-1

result:

ok answer is '-1'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

2 3
v..
...

output:

-1

result:

ok answer is '-1'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3536kb

input:

2 3
^<>
.^.

output:

-1

result:

ok answer is '-1'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3560kb

input:

2 3
vvv
<^<

output:

4

result:

ok answer is '4'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

4 3
v..
...
...
...

output:

-1

result:

ok answer is '-1'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

4 3
v..
<..
>>.
.v>

output:

9

result:

ok answer is '9'

Test #16:

score: 0
Accepted
time: 3ms
memory: 3568kb

input:

4 3
vv>
v><
<^>
<>>

output:

4

result:

ok answer is '4'

Test #17:

score: 0
Accepted
time: 14ms
memory: 3584kb

input:

25 50
>....................................v............
...............................<..................
........v.........................................
...........................^......................
..................................................
..........................................

output:

-1

result:

ok answer is '-1'

Test #18:

score: 0
Accepted
time: 14ms
memory: 3588kb

input:

50 25
v........................
.........................
...............>.........
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
...........

output:

-1

result:

ok answer is '-1'

Test #19:

score: 0
Accepted
time: 4ms
memory: 3604kb

input:

27 50
>..........................^......................
.........................<........................
..................................................
..................................................
...................................>..............
..........................................

output:

803

result:

ok answer is '803'

Test #20:

score: 0
Accepted
time: 30ms
memory: 3660kb

input:

50 27
v..........................
...........................
...........................
...........................
.............v.............
......................>....
...........................
...........................
..........^................
...........................
.................

output:

-1

result:

ok answer is '-1'

Test #21:

score: 0
Accepted
time: 64ms
memory: 3604kb

input:

50 50
^.................................................
....................................v.............
..................................................
.................................................>
..................................................
..........................................

output:

-1

result:

ok answer is '-1'

Test #22:

score: 0
Accepted
time: 91ms
memory: 3604kb

input:

49 50
>.................................................
..................................^...............
..................................................
..........<.......................................
..........................^.......................
..........................................

output:

-1

result:

ok answer is '-1'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3668kb

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: 3592kb

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: 1ms
memory: 3600kb

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: 3ms
memory: 3596kb

input:

50 27
<.v.....<....>^....<>......
>..^<........>...^.....^v..
........^....<<............
.<...>......^..............
......^....................
.........v.>>..............
......v.............v....>.
..........................>
......>...............v....
.......................^...
....v...<........

output:

94

result:

ok answer is '94'

Test #27:

score: 0
Accepted
time: 205ms
memory: 3676kb

input:

50 50
^..........>^............<............<.......^...
.....<.......>.v........................<........>
.................>................................
........................................>.........
.....>....>.......<...........v.....v<...v....^...
>....................<..............^.....

output:

-1

result:

ok answer is '-1'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

49 50
<.........^..................>...........^........
.....................v........................>...
.......<.>.>............>v........................
.v.v...<...........................>.<......^.....
.........<.......>...................>............
.......................v...........v......

output:

210

result:

ok answer is '210'

Test #29:

score: 0
Accepted
time: 3ms
memory: 3596kb

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: 3584kb

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: 3ms
memory: 3636kb

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: 0ms
memory: 3596kb

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: 3ms
memory: 3548kb

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: 3ms
memory: 3576kb

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: 1ms
memory: 3600kb

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: 3ms
memory: 3688kb

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'