UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212778#3828. Btwc200ms1252kbC++111.0kb2024-10-20 11:05:022024-10-20 14:38:05

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,n,m,dir[][2]={0,1,1,0,-1,0,0,-1};
void dfs(int x,int y,vector<int>& k,vector<vector<int>>& a,vector<int>& ans){
	int cnt=0;
	for(int i=0;i<4;i++){
		int dx=x+dir[i][0],dy=y+dir[i][1];
		if((dx<1&&dx>n&&dy<1&&dy>m)||a[x][y]>a[dx][dy]) cnt++;
	}
	if(cnt==4){
		if(k.size()>ans.size()) ans=k;
		if(k.size()==ans.size()) ans=min(ans,k);
		return;
	}
	for(int i=0;i<4;i++){
		int dx=x+dir[i][0],dy=y+dir[i][1];
		if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]>a[x][y]){
			k.push_back(a[dx][dy]);
			dfs(dx,dy,k,a,ans);
			k.pop_back();
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		vector<int> ans,k;
		vector<vector<int>> a(n+5,vector<int>(m+5,0));
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				k.push_back(a[i][j]);
				dfs(i,j,k,a,ans);
				k.pop_back();
			}
		cout<<ans.size()<<endl;
		for(auto &&i:ans) cout<<i<<' ';
		cout<<endl;
	}
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1252kb

input:

10
3 3
0 1 2
3 4 5
6 7 8
3 3
0 1 2
3 4 5
6 8 7
3 3
0 1 2
3 4 5
7 6 8
3 3
0 1 2
3 4 5
7 8 6
3 3
0 1 2...

output:

5
0 1 2 5 8 
6
0 1 2 5 7 8 
5
0 1 2 5 8 
6
0 1 2 5 6 8 
5
0 1 2 5 7 
7
0 1 2 5 6 7 8 
5
0 1 2 6 8 
6...

result:

ok 64 numbers

Test #2:

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

input:

10
1 10
1 5 0 8 2 9 6 3 4 7
1 10
2 5 8 0 9 7 3 1 6 4
3 3
0 1 2
5 4 3
6 7 8
1 10
3 4 7 2 5 6 9 0 1 8
...

output:

3
3 4 7 
4
1 3 7 9 
9
0 1 2 3 4 5 6 7 8 
4
2 5 6 9 
3
1 7 9 
4
4 5 6 7 
3
0 4 7 
10
0 1 2 3 4 5 6 7 ...

result:

ok 63 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Test #3:

score: 0
Time Limit Exceeded

input:

10
22 45
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

10
2 100000
143604 106821 145034 44402 118718 156663 77133 28800 81890 12336 191537 118894 103331 75...

output:

13
11306 16007 49522 70570 76999 90088 97453 105217 116458 118241 145649 165150 168193 
9
9688 35806...

result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

10
1 200000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #7:

score: 0
Time Limit Exceeded

input:

10
145 1379
140324 86968 96426 123781 39754 103720 60835 118904 114639 53717 27146 110309 39232 5608...

output:

14
8850 11113 25989 34151 36456 84869 93686 115053 144522 160408 175609 177211 186680 198340 
14
701...

result: