QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#41762	#3836. So I'll Max Out My Constructive Algorithm Skills	zhangchi	WA	850ms	3788kb	C++	1.7kb	2022-08-01 09:30:31	2022-08-01 09:30:32

Judging History

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

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

[2022-08-01 09:30:32]
评测

测评结果：WA
用时：850ms
内存：3788kb

查看

[2022-08-01 09:30:31]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,T,ans[10005],maze[66][66];
bool m[66][66],check; 
void dfs(int num,int x,int y,int k){
	m[x][y]=1;
	ans[num]=maze[x][y];
	//printf("%d %d %d %d %d\n",num,x,y,k,maze[x][y]);
	if(check==1){
		return;
	}
	if(num==n*n&&k>=0){
		check=1;
		return;
	}
	else {
		if(m[x+1][y]==0&&maze[x+1][y]!=0&&check==0){
			if(maze[x][y]<maze[x+1][y]){	
				dfs(num+1,x+1,y,k-1);
			}
			else{
				dfs(num+1,x+1,y,k+1);
			}
			m[x+1][y]=0;
			if(check==0){
				ans[num+1]=0;
			}
		}
		if(m[x][y+1]==0&&maze[x][y+1]!=0&&check==0){
			if(maze[x][y]<maze[x][y+1]){	
				dfs(num+1,x,y+1,k-1);
			}
			else{
				dfs(num+1,x,y+1,k+1);
			}
			m[x][y+1]=0;
			if(check==0){
				ans[num+1]=0;
			}
		}
		if(m[x-1][y]==0&&maze[x-1][y]!=0&&check==0){
			if(maze[x][y]<maze[x-1][y]){	
				dfs(num+1,x-1,y,k-1);
			}
			else{
				dfs(num+1,x-1,y,k+1);
			}
			m[x-1][y]=0;
			if(check==0){
				ans[num+1]=0;
			}
		}
		if(m[x][y-1]==0&&maze[x][y-1]!=0&&check==0){
			if(maze[x][y]<maze[x][y-1]){	
				dfs(num+1,x,y-1,k-1);
			}
			else{
				dfs(num+1,x,y-1,k+1);
			}
			m[x][y-1]=0;
			if(check==0){
				ans[num+1]=0;
			}
		}
	}
}
int main(){
	scanf("%d",&T);
	for(int t=0;t<T;t++){
		check=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&maze[i][j]);
			} 
		}
		memset(m,0,sizeof(m));
		for(int i=0;i<=n+1;i++){
			m[i][0]=1;
			m[0][i]=1;
			m[i][n+1]=1;
			m[n+1][i]=1;
		}
		dfs(1,1,1,0);
		printf("%d",ans[1]);
		for(int i=2;i<=n*n;i++){
			printf(" %d",ans[i]);
		}
		if(t!=T-1)cout<<endl;
	}
} 
/*
4
2
4 3
2 1
2
4 2
3 1
3
9 8 5
1 7 6
3 2 4
2
4 3
2 1
*/

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3656kb

input:

output:

4 2 1 3

result:

ok correct

Test #2:

score: -100

Wrong Answer

time: 850ms

memory: 3788kb

input:

100
9
30 75 35 51 25 19 76 65 62
11 56 63 60 77 48 28 26 74
16 44 46 41 17 8 66 61 42
29 7 43 38 40 31 27 10 39
52 23 58 80 50 20 33 69 47
79 1 5 49 22 37 71 18 70
54 72 4 64 55 34 12 6 15
14 53 45 13 32 59 73 57 81
36 3 78 24 2 68 9 67 21
7
11 28 2 19 9 41 24
17 34 5 10 42 18 47
33 35 22 8 49 1 29
...

output:

30 11 16 29 52 79 54 14 36 3 78 24 2 68 9 67 21 81 15 70 47 39 42 74 62 65 26 61 10 69 18 6 57 73 12 71 33 27 66 28 76 19 48 8 31 20 37 34 59 32 55 22 50 40 17 77 25 51 60 41 38 80 49 64 13 45 4 5 58 43 46 63 35 75 56 44 7 23 1 72 53
11 17 33 14 39 46 21 31 23 40 38 15 4 13 30 26 29 47 24 41 18 1 7 ...

result:

wrong answer Integer 0 violates the range [1, 4]