bravearmycode

mail@pastecode.io avatar
unknown
plain_text
6 months ago
1.1 kB
0
Indexable
Never
#include <iostream>
using namespace std;
int map[55][55];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
bool visited[55][55];
int res;
int N, M;
int X,Y;
void dfs(int x, int y, int currMap, int square){
	res = max(res,square);
	int nx, ny;
	for (int i = 0; i < 4; i++)
	{
		nx = x + dx[i];
		ny = y + dy[i];
		if (nx < 0 || nx >= N || ny >= M || ny < 0) continue;
		if(visited[nx][ny] == 0 && currMap >= map[nx][ny] && map[nx][ny] != 0){
			if(map[nx][ny] > currMap/2){
					visited[nx][ny] = true;
					dfs(nx,ny,currMap - map[nx][ny],square+1);
					visited[nx][ny] = false;
			}else if(map[nx][ny] <= currMap / 2)
			{
					visited[nx][ny] = true;
					dfs(nx,ny,currMap + map[nx][ny],square+1);
					visited[nx][ny] = false;
			}
		}
	}
}
int main(){
	int T;
	freopen("input.txt","r",stdin);
	cin>>T;
	for (int i = 0; i < T; i++)
	{
		cin>>N>>M>>X>>Y;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin>>map[i][j];
				visited[i][j] = false;
			}
		}
		res = 0;
		visited[X-1][Y-1] = true;
		dfs(X-1,Y-1,map[X-1][Y-1],1);
		cout<<res<<endl;
	}
	return 0;
}
Leave a Comment