QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799845#1453. Froggerucup-team1134#AC ✓251ms72696kbC++232.4kb2024-12-05 18:44:342024-12-05 18:44:35

Judging History

This is the latest submission verdict.

  • [2024-12-05 18:44:35]
  • Judged
  • Verdict: AC
  • Time: 251ms
  • Memory: 72696kb
  • [2024-12-05 18:44:34]
  • Submitted

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'