QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91530#4231. Rafting TripFHQYTL 13ms14296kbC++172.7kb2023-03-29 02:15:072023-03-29 02:15:09

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 02:15:09]
  • 评测
  • 测评结果:TL
  • 用时:13ms
  • 内存:14296kb
  • [2023-03-29 02:15:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=509;
int ans,res,f1,f2,p1,p2,p3,p4,xx,yy,pre,px,py,f;
int sign[maxn][maxn];
int mp[maxn][maxn];
int d[maxn][maxn];
//int pd[maxn][maxn];
int sx[4]={-1,0,1,0};
int sy[4]={0,1,0,-1};
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
bool check(int x,int y)
{
	if(mp[x][y]!=-1)
	{
		p1=mp[x][y];
		p2=(p1+2)%4;
		if(mp[x+sx[p1]][y+sy[p1]]==-1)
			return true;
	}
	return false;
}
void dfs1(int x,int y)
{
	//	if(sign[x][y])
	//		return;
	sign[x][y]=1;
	int bid[4];
	for(int t=0;t<4;t++)
	{
		bid[t]=d[x+sx[t]][y+sy[t]];
		d[x+sx[t]][y+sy[t]]=0;
		ans+=bid[t];
	}
	for(int t=0;t<4;t++)
	{
		p1=(t+2)%4;
		if(mp[x+sx[t]][y+sy[t]]==p1)
			dfs1(x+sx[t],y+sy[t]);
	}
	res=max(res,ans);
	for(int t=0;t<4;t++)
	{
		d[x+sx[t]][y+sy[t]]=bid[t];
		ans-=bid[t];
	}
	return;
}
void dfs2(int x,int y)
{
	//	if(d[x][y]==-1)
	//		return;
	if(sign[x][y])
	{
		f1=x;
		f2=y;
		return;
	}
	sign[x][y]=1;
	p1=mp[x][y];
	dfs2(x+sx[p1],y+sy[p1]);
	sign[x][y]=0;
	return;
}
void dfs3(int x,int y)
{
	sign[x][y]=1;
	if(x==f1&&y==f2&&f)
	{
		px=x;
		py=y;
		int st=0;
		while(st==0||(!(px==f1&&py==f2)))
		{
			st++;
			for(int t=0;t<4;t++)
			{
				if(!sign[x+sx[t]][y+sy[t]]&&mp[x+sx[t]][y+sy[t]]!=-1&&mp[x+sx[t]][y+sy[t]]==(t+2)%4)
				{
					dfs1(x+sx[t],y+sy[t]);
				}
			}
		}
		return;
	}
	f=1;
	p1=mp[x][y];
	int bid[4];
	for(int t=0;t<4;t++)
	{
		bid[t]=d[x+sx[t]][y+sy[t]];
		d[x+sx[t]][y+sy[t]]=0;
		ans+=bid[t];
	}
	dfs3(x+sx[p1],y+sy[p1]);
	res=max(res,ans);
	for(int t=0;t<4;t++)
	{
		d[x+sx[t]][y+sy[t]]=bid[t];
		ans-=bid[t];
	}
	return;
}
int main()
{
//	freopen("rand.out","r",stdin);
//	freopen("my.out","w",stdout);
	int a,b;
	res=0;
	cin>>a>>b;
	memset(mp,-1,sizeof(mp));
	for(int x=1;x<=a;x++)
	{
		string str;
		cin>>str;
		for(int t=1;t<=b;t++)
		{
			if(str[t-1]=='>')
				mp[x][t]=1;
			else if(str[t-1]=='^')
				mp[x][t]=0;
			else if(str[t-1]=='<')
				mp[x][t]=3;
			else if(str[t-1]=='v')
				mp[x][t]=2;
			else if(str[t-1]=='#')
				d[x][t]=1;
		}
		
	}
	for(int x=1;x<=a;x++)
	{
		for(int y=1;y<=b;y++)
		{
			if(check(x,y))
			{
				int bid[4];
				ans=0;
				dfs1(x,y);
				res=max(res,ans);
			}
		}
	}
	for(int x=1;x<=a;x++)
	{
		for(int y=1;y<=b;y++)
		{
			if(!sign[x][y]&&mp[x][y]!=-1)
			{
				dfs2(x,y);
				ans=0;
				f=0;
				dfs3(f1,f2);
			}
		}
	}
	cout<<res<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 3ms
memory: 4516kb

input:

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

output:

2

result:

ok single line: '2'

Test #3:

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

input:

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

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 3ms
memory: 5528kb

input:

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

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 2ms
memory: 4484kb

input:

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

output:

2

result:

ok single line: '2'

Test #6:

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

input:

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

output:

6

result:

ok single line: '6'

Test #7:

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

input:

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

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4456kb

input:

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

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 3ms
memory: 4492kb

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 3ms
memory: 4440kb

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 13ms
memory: 11588kb

input:

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

output:

41195

result:

ok single line: '41195'

Test #12:

score: 0
Accepted
time: 13ms
memory: 14296kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

24926

result:

ok single line: '24926'

Test #13:

score: -100
Time Limit Exceeded

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:


result: