QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#14898 | #1453. Frogger | Qingyu | AC ✓ | 205ms | 3760kb | C++20 | 1.2kb | 2021-10-25 12:44:01 | 2022-05-17 01:13:50 |
Judging History
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'