Untitled

mail@pastecode.io avatar
unknown
plain_text
11 days ago
2.3 kB
1
Indexable
Never
#include <iostream>
using namespace std;
struct Point
{
	int hang,cot;
};
Point queue[10000000];
struct Queue
{
	int rear, front;
	Queue()
	{
		rear = front = 0;
	}
	void push(Point a)
	{
		queue[rear] = a;
		rear++;
	}
	Point pop()
	{
		Point a;
		a = queue[front];
		front++;
		return a;
	}
	bool isEmpty()
	{
		if(rear == front) return true;
		else return false;
	}
};
int N,M;
Point vt_do, vt_rong;
int map[3030][3030];
int visit[3030][3030];
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};
void BFS()
{
	Queue Q = Queue();
	Q.push(vt_do);
	visit[vt_do.hang][vt_do.cot] = 1;
	while(!Q.isEmpty())
	{
		Point p = Q.pop();
		for(int i = 0; i<4;i++)
		{
			int h = p.hang + dx[i];
			int c = p.cot + dy[i];
			if(h >= 1 && h <= N && c >= 1 && c <= M && visit[h][c] == 0 && map[h][c] != 0 && map[h][c] != 2)
			{
				visit[h][c] = visit[p.hang][p.cot]+1;
				Point tp;
				tp.hang = h;
				tp.cot = c;
				Q.push(tp);
			}
		}
	}
}
int check_full_map()
{
	int max = 0;
	for(int i = 1; i<= N; i++)
	{
		for(int j = 1; j<= M; j++)
		{
			if(map[i][j] != 0 && visit[i][j] != 0 && map[i][j] != 2)
			{
				if(visit[i][j] > max)
				{
					max = visit[i][j];
				}
			}
			else if(map[i][j] != 0 && visit[i][j] == 0 && map[i][j] != 2)
			{
				return -1;
			}
		}
	}
	return max;
}
int check_day_cell()
{
	int max = 0;
	for(int i = 0; i<4; i++)
	{
		if(visit[vt_rong.hang + dx[i]][vt_rong.cot + dy[i]] == 0)
		{
			return -1;
		}
		else
		{
			if(visit[vt_rong.hang + dx[i]][vt_rong.cot + dy[i]] > max)
			{
				max = visit[vt_rong.hang + dx[i]][vt_rong.cot + dy[i]];
			}
		}
	}
	return max;
}
int main()
{
	//freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++)
	{
		cin >> N >> M;
		cin >> vt_do.hang >> vt_do.cot;
		for(int i = 1; i<=N; i++)
		{
			for(int j = 1;j<=M; j++)
			{
				cin >> map[i][j];
				if(map[i][j] == 2)
				{
					vt_rong.hang = i;
					vt_rong.cot = j;
				}
			}
		}
		for(int i = 1; i<=N; i++)
		{
			for(int j = 1;j<=M; j++)
			{
				visit[i][j] = 0;
			}
		}
		BFS();
		cout << "Case #" << tc << endl;
		int check_full = check_day_cell();
		int full_map = check_full_map();
		if(check_full == -1)
		{
			cout << "-1 -1" << endl;
		}
		else
		{
			cout << check_full << " " << full_map << endl;
		}
	}
	return 0;
}
Leave a Comment