QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#55419	#4231. Rafting Trip	Kieray^#	TL	2ms	3828kb	C++	1.7kb	2022-10-13 17:29:57	2022-10-13 17:30:00

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-10-13 17:30:00]
评测

测评结果：TL
用时：2ms
内存：3828kb

查看

[2022-10-13 17:29:57]
提交

answer

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<numeric>
#include<cmath>
using namespace std;
#define ll long long
#define ge getchar 
#define pun putchar('\n')
#define pu putchar
#define puk putchar(' ')
#define pb push_back
typedef vector<int> vint;
typedef array<int,2> pii;
const int nn=505;
int n,m,a[nn][nn],ind[nn][nn];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
bool b[nn][nn];
int f[nn][nn];
pii q[nn*nn];int lq;
int ss=0,mx=0;
void ff(int i,int j){
	b[i][j]=1;f[i][j]=0;q[++lq]={i,j};
	for(int k=1;k<=4;k++){
		int x=i+dx[k];
		int y=j+dy[k];
		if(a[x][y]==-1){
			ss++;
		}
	}
	int k=a[i][j];
	int x=i+dx[k];
	int y=j+dy[k];
	if(!b[x][y]&&a[x][y]>0){
		if(f[x][y]<0||f[x][y]+ss>mx){
			ff(x,y);
			f[i][j]=f[x][y];
		}
	}
	for(int k=1;k<=4;k++){
		int x=i+dx[k];
		int y=j+dy[k];
		if(a[x][y]==-1&&!b[x][y]){
			b[x][y]=1;
			q[++lq]={x,y};
			f[i][j]++;
		}
	}
	mx=max(mx,f[i][j]);
	//cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		char c=ge();while(c<'#')c=ge();
		for(int j=1;j<=m;j++){f[i][j]=-1;
			if(c=='.')a[i][j]=-2;
			if(c=='#')a[i][j]=-1;
			if(c=='^')a[i][j]=1;
			if(c=='v')a[i][j]=2;
			if(c=='<')a[i][j]=3;
			if(c=='>')a[i][j]=4;
			c=ge();
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)if(a[i][j]>0&&f[i][j]<0){
			int ok=0;
			for(int k=1;k<=4;k++){
				int x=i+dx[k];
				int y=j+dy[k];
				if(a[x][y]==-1){
					ok=1;
				}
			}
			if(ok){
				lq=0;ff(i,j);
				for(int l=1;l<=lq;l++){
					b[q[l][0]][q[l][1]]=0;
				}
			}
		}
	cout<<mx<<endl;

	return 0;
}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 3740kb

input:

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

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 2ms

memory: 3700kb

input:

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

output:

result:

ok single line: '2'

Test #3:

score: 0

Accepted

time: 2ms

memory: 3776kb

input:

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

output:

result:

ok single line: '5'

Test #4:

score: 0

Accepted

time: 2ms

memory: 3784kb

input:

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

output:

result:

ok single line: '2'

Test #5:

score: 0

Accepted

time: 2ms

memory: 3748kb

input:

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

output:

result:

ok single line: '2'

Test #6:

score: 0

Accepted

time: 2ms

memory: 3648kb

input:

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

output:

result:

ok single line: '6'

Test #7:

score: 0

Accepted

time: 2ms

memory: 3736kb

input:

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

output:

result:

ok single line: '3'

Test #8:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

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

output:

result:

ok single line: '4'

Test #9:

score: 0

Accepted

time: 2ms

memory: 3640kb

input:

2 2
>.
.#

output:

result:

ok single line: '0'

Test #10:

score: 0

Accepted

time: 2ms

memory: 3720kb

input:

2 2
..
.v

output:

result:

ok single line: '0'

Test #11:

score: -100

Time Limit Exceeded

input:

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