QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91955#4231. Rafting TripFHQYTL 2ms5488kbC++203.3kb2023-03-29 23:44:382023-03-29 23:44:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 23:44:41]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:5488kb
  • [2023-03-29 23:44:38]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...

output:


result: