UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212757#3828. B1801553680400ms1252kbC++111.2kb2024-10-20 10:36:062024-10-20 14:37:16

answer

#include <bits/stdc++.h>
using namespace std;

int t,n,m,dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}};
vector<vector<int> >a;
vector<int>tmp,ans;

void dfs(int x,int y)
{
	tmp.push_back(a[x][y]);
	int cnt = 0;
	for(int i = 0;i < 4;i++)
	{
		int tx = x + dir[i][0],ty = y + dir[i][1];
		if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] > a[x][y])
		{
			cnt++;
			dfs(tx,ty);
		}
	}
	if(!cnt)
	{
		if(tmp.size() > ans.size())
			ans = tmp;
		else if(tmp.size() == ans.size())
		{
			int l = tmp.size(),isok = 0;
			for(int i = 0;i < l;i++)
			{
				if(tmp[i] < ans[i])
				{
					isok = 1;
					break;
				}
				if(tmp[i] > ans[i])
					break;
			}
			if(isok)
				ans = tmp;
		}
	}
	tmp.pop_back();
}

int main()
{
	cin >> t;
	while(t--)
	{
		tmp.clear(),ans.clear(),a.clear();
		cin >> n >> m;
		int x1,y1;
		a.push_back({0});
		for(int i = 1;i <= n;i++)
		{
			a.push_back({0});
			for(int j = 1;j <= m;j++)
			{
				int q;
				cin >> q;
				if(!q)
					x1 = i,y1 = j;
				a[i].push_back(q);
			}
		}
		dfs(x1,y1);
		cout << ans.size() << endl;
		for(auto i : ans)
			cout << i << ' ';
		cout << endl;
	}
	return 0;
}

Details

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

Subtask #1:

score: 0
Wrong Answer

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: -20
Wrong Answer
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:

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

result:

wrong answer 1st numbers differ - expected: '3', found: '2'

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:

4
0 25881 84639 130474 
3
0 52559 71075 
4
0 87520 175520 189775 
2
0 102185 
3
0 34497 47197 

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:

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

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:

6
0 36399 40625 84019 90544 113072 
4
0 32415 107338 142810 
5
0 45890 58142 159235 175422 
6
0 1864...

result: