QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#349763#4231. Rafting TripLaStataleBlueTL 0ms3796kbC++232.1kb2024-03-10 05:12:332024-03-10 05:12:34

Judging History

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

  • [2024-03-10 05:12:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3796kb
  • [2024-03-10 05:12:33]
  • 提交

answer

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

void solve([[maybe_unused]] int t){
    const int N = 500;
    
    int r,c;
    cin>>r>>c;
    
    auto id = [&](int x,int y)->int{
        if(x<0 || x>=r || y<0 || y>=c)return -1;
        return x*c+y;
    };
    
    vector opz(r*c,unordered_set<int>());
    
    vector mat(r,vector(c,'.'));
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>mat[i][j];
        }
    }
    
    const vector<array<int,2>> dir = {{-1,0},{1,0},{0,-1},{0,1}};
    vector succ(r*c,-1);
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(mat[i][j]=='>' && id(i,j+1)!=-1 && mat[i][j+1]!='#' && mat[i][j+1]!='.')succ[id(i,j)]=id(i,j+1);
            if(mat[i][j]=='<' && id(i,j-1)!=-1 && mat[i][j-1]!='#' && mat[i][j-1]!='.')succ[id(i,j)]=id(i,j-1);
            if(mat[i][j]=='^' && id(i-1,j)!=-1 && mat[i-1][j]!='#' && mat[i-1][j]!='.')succ[id(i,j)]=id(i-1,j);
            if(mat[i][j]=='v' && id(i+1,j)!=-1 && mat[i+1][j]!='#' && mat[i+1][j]!='.')succ[id(i,j)]=id(i+1,j);
            
            for(auto [dx,dy] : dir){
                if(id(i+dx,j+dy)!=-1 && mat[i+dx][j+dy]=='#'){
                    opz[id(i,j)].insert(id(i+dx,j+dy));
                }
            }
        }
    }
    vector vis(r*c,0);
    
    auto dfs = [&](auto &dfs,int nodo)->void{
        if(vis[nodo]==3)return;
        vis[nodo]++;
        
        if(succ[nodo]!=-1){
            dfs(dfs,succ[nodo]);
            for(auto x : opz[succ[nodo]]){
                opz[nodo].insert(x);
            }
            //opz[nodo]|=opz[succ[nodo]];
        }
        
        vis[nodo]=3;
    };
    
    int ans=0;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(mat[i][j]!='#'&& mat[i][j]!='.'){
                dfs(dfs,id(i,j));
                ans=max(ans,(int)opz[id(i,j)].size());
            }
        }
    }
    
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

output:

4

result:

ok single line: '4'

Test #2:

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

input:

4 5
>v<<.
^<..#
#...#
.#>^#

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

4 6
>>v#>v
^#>>^v
^<<#v<
.#^<<#

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

6 6
^.>>>>
^.....
^....v
^....v
#....v
<<<<#v

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

6 7
^>>>>>v
^.....v
^.#^..v
^.#^<.v
^.....v
^<<<<<<

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

3 7
>v<<<<#
^<#####
#^<<<<<

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

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

output:

3

result:

ok single line: '3'

Test #8:

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

input:

7 3
###
#>#
###
...
###
#>.
###

output:

4

result:

ok single line: '4'

Test #9:

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

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

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

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: -100
Time Limit Exceeded

input:

498 498
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...

output:


result: