QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91955 | #4231. Rafting Trip | FHQY | TL | 2ms | 5488kb | C++20 | 3.3kb | 2023-03-29 23:44:38 | 2023-03-29 23:44:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int n,m;
char tu[510][510];
int ans=0;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
map<char,int>fr={{'>',0},{'v',1},{'<',2},{'^',3}};
map<pair<int,int>,set<pair<int,int>>>start;
bool used[510][510],f_used[510][510];
pair<int,int>b[510][510];
bool is_end(int x,int y)
{
char f=tu[x][y];
if(f=='>'||f=='v'||f=='<'||f=='^')
{
int pos=fr[f];
int nx=x+dx[pos];
int ny=y+dy[pos];
char nex=tu[nx][ny];
if(nex=='.'||nex=='#'||nx==0||nx==n+1||ny==0||ny==m+1) return 1;
}
return 0;
}
void forward_dfs(int x,int y,bool &ok,int &sx,int &sy)
{
// cout<<"debug:head ("<<x<<","<<y<<")"<<endl;
if(x==0||x==n+1||y==0||y==m+1) return;
if(is_end(x,y))
{
for(int t=0;t<4;t++)
{
int nx=x+dx[t];
int ny=y+dy[t];
if(tu[nx][ny]=='#') start[{x,y}].insert({nx,ny});
}
}
// cout<<"debug:f_used["<<x<<"]["<<y<<"]="<<f_used[x][y]<<endl;
if(f_used[x][y]==1)
{
ok=1;
// cout<<"debug:ok="<<ok<<endl;
sx=x;
sy=y;
return;
}
f_used[x][y]=1;
if(used[x][y]) return;
used[x][y]=1;
if(tu[x][y]=='>') forward_dfs(x,y+1,ok,sx,sy);
if(tu[x][y]=='v') forward_dfs(x+1,y,ok,sx,sy);
if(tu[x][y]=='<') forward_dfs(x,y-1,ok,sx,sy);
if(tu[x][y]=='^') forward_dfs(x-1,y,ok,sx,sy);
// cout<<"debug:back ("<<x<<","<<y<<") ok="<<ok<<endl;
if(ok)
{
for(int t=0;t<4;t++)
{
int nx=x+dx[t];
int ny=y+dy[t];
if(tu[nx][ny]=='#') start[{sx,sy}].insert({nx,ny});
}
}
}
void get_start()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
bool ok=0;
int sx=-1,sy=-1;
if(!used[i][j])forward_dfs(i,j,ok,sx,sy);
}
}
}
//记得清空used
void back_dfs(int x,int y,int cnt)
{
if(tu[x][y]=='.'||tu[x][y]=='#'||x==0||x==n+1||y==0||y==m+1)
{
ans=max(ans,cnt);
return;
}
if(used[x][y])return;
used[x][y]=1;
for(int t=0;t<4;t++)
{
int nx=x+dx[t];
int ny=y+dy[t];
if(tu[nx][ny]=='#'&&(!used[nx][ny]))
{
used[nx][ny]=1;
b[nx][ny]={x,y};
cnt++;
}
}
for(int t=0;t<4;t++)
{
int px=x+dx[t];
int py=y+dy[t];
if(px==0||px==n+1||py==0||py==m+1||tu[px][py]=='.'||tu[px][py]=='#')
{
back_dfs(px,py,cnt);
}
int pos=fr[tu[px][py]];
if(px+dx[pos]==x&&py+dy[pos]==y)
{
back_dfs(px,py,cnt);
for(int k=0;k<4;k++)
{
int nx=px+dx[k];
int ny=py+dy[k];
pair<int,int> p={px,py};
if(tu[nx][ny]=='#'&&b[nx][ny]==p)
{
used[nx][ny]=0;
b[nx][ny]={0,0};
}
}
}
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>tu[i][j];
}
}
get_start();
// for(auto [p,s] : start)
// {
// auto [x,y]=p;
// cout<<"debug:("<<x<<","<<y<<"):->";
// for(auto [nx,ny] : s)
// {
// cout<<" ("<<nx<<","<<ny<<")";
// }
// cout<<endl;
// }
for(auto [p,s] : start)
{
auto [x,y]=p;
int cnt=0;
memset(used,0,sizeof used);
for(auto [nx,ny] : s)
{
cnt++;
used[nx][ny]=1;
b[nx][ny]={x,y};
}
back_dfs(x,y,cnt);
for(auto [nx,ny] : s)
{
used[nx][ny]=0;
b[nx][ny]={0,0};
}
}
cout<<ans<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3820kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5488kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: -100
Time Limit Exceeded
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...