QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799845 | #1453. Frogger | ucup-team1134# | AC ✓ | 251ms | 72696kb | C++23 | 2.4kb | 2024-12-05 18:44:34 | 2024-12-05 18:44:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=55,INF=15<<26;
int dis[MAX][MAX][MAX*MAX];
bool iru[MAX][MAX][MAX*MAX][4];
string U=">v<^";
vi dh={0,1,0,-1},dw={1,0,-1,0};
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int H,W;cin>>H>>W;
vector<string> S(H);
for(int i=0;i<H;i++){
cin>>S[i];
for(int j=0;j<W;j++){
for(int k=0;k<4;k++){
if(S[i][j]==U[k]) iru[i][j][0][k]=1;
}
}
}
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
for(int x=0;x<MAX*MAX;x++) dis[i][j][x]=INF;
}
}
for(int t=0;t<H*W;t++){
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
for(int k=0;k<4;k++){
iru[(i+dh[k]+H)%H][(j+dw[k]+W)%W][(t+1)%(H*W)][k]|=iru[i][j][t][k];
}
}
}
}
queue<array<int,3>> Q;
dis[0][0][0]=0;
Q.push({0,0,0});
while(!Q.empty()){
auto [h,w,ama]=Q.front();Q.pop();
int d=dis[h][w][ama];
for(int k=0;k<4;k++){
if(iru[h][w][ama][k]){
int toh=(h+dh[k]+H)%H,tow=(w+dw[k]+W)%W;
if(chmin(dis[toh][tow][(ama+1)%(H*W)],d+1)) Q.push({toh,tow,(ama+1)%(H*W)});
}
}
}
int ans=INF;
for(int t=0;t<H*W;t++){
for(int k=0;k<4;k++){
chmin(ans,dis[H-1][W-1][t]);
}
}
if(ans==INF) ans=-1;
cout<<ans<<endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7704kb
input:
3 5 >^..v ...<. .v..^
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9720kb
input:
3 5 <.... .v... ...>.
output:
31
result:
ok answer is '31'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
2 2 >< ><
output:
-1
result:
ok answer is '-1'
Test #4:
score: 0
Accepted
time: 99ms
memory: 66868kb
input:
49 50 <................................................. .v................................................ .................................................. .................................................. .................................................. ..........................................
output:
4946
result:
ok answer is '4946'
Test #5:
score: 0
Accepted
time: 94ms
memory: 67700kb
input:
50 49 <................................................ .v............................................... ................................................. ................................................. ................................................. ...............................................
output:
4945
result:
ok answer is '4945'
Test #6:
score: 0
Accepted
time: 111ms
memory: 68272kb
input:
50 50 <................................................. .v................................................ .................................................. .................................................. .................................................. ..........................................
output:
146
result:
ok answer is '146'
Test #7:
score: 0
Accepted
time: 80ms
memory: 63724kb
input:
47 48 <............................................... .v.............................................. ................................................ ................................................ ................................................ ................................................ ...
output:
4556
result:
ok answer is '4556'
Test #8:
score: 0
Accepted
time: 0ms
memory: 5904kb
input:
2 2 ^. ..
output:
-1
result:
ok answer is '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
2 2 ^v ^.
output:
-1
result:
ok answer is '-1'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7696kb
input:
2 2 ^v <v
output:
-1
result:
ok answer is '-1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
2 3 v.. ...
output:
-1
result:
ok answer is '-1'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7696kb
input:
2 3 ^<> .^.
output:
-1
result:
ok answer is '-1'
Test #13:
score: 0
Accepted
time: 1ms
memory: 7976kb
input:
2 3 vvv <^<
output:
4
result:
ok answer is '4'
Test #14:
score: 0
Accepted
time: 1ms
memory: 7940kb
input:
4 3 v.. ... ... ...
output:
-1
result:
ok answer is '-1'
Test #15:
score: 0
Accepted
time: 1ms
memory: 9748kb
input:
4 3 v.. <.. >>. .v>
output:
9
result:
ok answer is '9'
Test #16:
score: 0
Accepted
time: 0ms
memory: 9808kb
input:
4 3 vv> v>< <^> <>>
output:
4
result:
ok answer is '4'
Test #17:
score: 0
Accepted
time: 23ms
memory: 36344kb
input:
25 50 >....................................v............ ...............................<.................. ........v......................................... ...........................^...................... .................................................. ..........................................
output:
-1
result:
ok answer is '-1'
Test #18:
score: 0
Accepted
time: 19ms
memory: 61204kb
input:
50 25 v........................ ......................... ...............>......... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ...........
output:
-1
result:
ok answer is '-1'
Test #19:
score: 0
Accepted
time: 23ms
memory: 40568kb
input:
27 50 >..........................^...................... .........................<........................ .................................................. .................................................. ...................................>.............. ..........................................
output:
803
result:
ok answer is '803'
Test #20:
score: 0
Accepted
time: 30ms
memory: 62564kb
input:
50 27 v.......................... ........................... ........................... ........................... .............v............. ......................>.... ........................... ........................... ..........^................ ........................... .................
output:
-1
result:
ok answer is '-1'
Test #21:
score: 0
Accepted
time: 85ms
memory: 72280kb
input:
50 50 ^................................................. ....................................v............. .................................................. .................................................> .................................................. ..........................................
output:
-1
result:
ok answer is '-1'
Test #22:
score: 0
Accepted
time: 94ms
memory: 70348kb
input:
49 50 >................................................. ..................................^............... .................................................. ..........<....................................... ..........................^....................... ..........................................
output:
-1
result:
ok answer is '-1'
Test #23:
score: 0
Accepted
time: 26ms
memory: 39652kb
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: 22ms
memory: 71868kb
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: 34ms
memory: 41104kb
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: 32ms
memory: 71592kb
input:
50 27 <.v.....<....>^....<>...... >..^<........>...^.....^v.. ........^....<<............ .<...>......^.............. ......^.................... .........v.>>.............. ......v.............v....>. ..........................> ......>...............v.... .......................^... ....v...<........
output:
94
result:
ok answer is '94'
Test #27:
score: 0
Accepted
time: 104ms
memory: 72696kb
input:
50 50 ^..........>^............<............<.......^... .....<.......>.v........................<........> .................>................................ ........................................>......... .....>....>.......<...........v.....v<...v....^... >....................<..............^.....
output:
-1
result:
ok answer is '-1'
Test #28:
score: 0
Accepted
time: 106ms
memory: 70260kb
input:
49 50 <.........^..................>...........^........ .....................v........................>... .......<.>.>............>v........................ .v.v...<...........................>.<......^..... .........<.......>...................>............ .......................v...........v......
output:
210
result:
ok answer is '210'
Test #29:
score: 0
Accepted
time: 39ms
memory: 39720kb
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: 44ms
memory: 71352kb
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: 60ms
memory: 43248kb
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: 54ms
memory: 69444kb
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: 149ms
memory: 72032kb
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: 193ms
memory: 69524kb
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: 184ms
memory: 72424kb
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: 251ms
memory: 69964kb
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'