Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.8 kB
3
Indexable
/* Ice Cave */
#include<iostream>
using namespace std;

typedef struct
{
	int x,y;
}o_xy;

int Map[105][105] ={0};
bool Vis[105][105] ={false};
o_xy Queue[100000];

int r = -1, f = -1;

int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};

void push(o_xy obj)
{
	r++;
	Queue[r].x = obj.x;
	Queue[r].y = obj.y;
}

void pop(o_xy &obj)
{
	f++;
	obj.x = Queue[f].x;
	obj.y = Queue[f].y;
}

void reset_Queue()
{
	r = f = -1;
	for(int i =0; i< 100000; i++)
	{
		Queue[i].x = 0;
		Queue[i].y = 0;
	}
}

void reset_Vis()
{
	r = f = -1;
	for(int i = 0; i< 105; i++)
	{
		for(int j =0; j< 105; j++)
		{
			Vis[i][j] = false;
		}
	}

}

int BFS(o_xy start, o_xy end, int n, int m)
{
	push(start);
	Vis[start.x][start.y] = true;

	o_xy pre;
	while(r != f)
	{
		pop(pre);
		for(int i =0; i< 4; i++)
		{
			o_xy next;
			next.x = pre.x + dx[i];
			next.y = pre.y + dy[i];

			if(next.x >= 0 && next.x < n && next.y >= 0 && next.y < m)
			{
				// kiem tra gap endpoint
				if(next.x == end.x && next.y == end.y)
				{
					if(Map[end.x][end.y] == 0)
					{
						return 0;
					}
					if(Map[end.x][end.y] == 1)
					{
						return 1;
					}
				}
				// gap duong di
				if(Map[next.x][next.y] == 1 && Vis[next.x][next.y] == false)
				{
					push(next);
					Vis[next.x][next.y] = true;
				}
			}
		}
	}
	return -1;
}

bool is_way_out(o_xy point_input)
{
	// must reset Queue
	push(point_input);

	o_xy pre;
	while (r != f)
	{
		pop(pre);

		for(int i =0; i< 4; i++)
		{
			o_xy next;
			next.x = pre.x + dx[i];
			next.y = pre.y + dy[i];

			if(Map[next.x][next.y] == 1 && Vis[next.x][next.y] == false)
			{
				push(next);
				Vis[next.x][next.y] = true;
			}
			if(next.x == point_input.x && next.y == point_input.y)
			{
				return true;
			}
		}
	}
	return false;
}


void input(int &n, int &m, o_xy &start, o_xy &end)
{
	cin>>n>>m;
	cin>>start.x>>start.y;
	cin>>end.x>>end.y;

	for(int i = 0; i< n; i++)
	{
		for(int j = 0; j< m; j++)
		{
			cin>>Map[i][j];
		}
	}

}

bool is_check_ans(int is_way, o_xy end_point)
{
	if(is_way == 1)
	{
		if(is_way_out(end_point))
		{
			return true;
		}
	} 
	else if(is_way == 0 )
	{
		return true;
	}
	else if(is_way == -1)
	{
		return false;
	}
}

int main()
{
	freopen("Text.txt","r",stdin);

	int T;
	int n,m;
	bool ans = false;
	o_xy start_point, end_point;
	cin>>T;

	for(int tc = 1; tc <= T; tc++)
	{
		// input
		input(n,m,start_point, end_point);
		// reset
		reset_Vis();
		// process
		int is_way_to_end_point = BFS(start_point, end_point, n, m);
		// check end_point la 0 hay -1
		if(is_check_ans(is_way_to_end_point, end_point))
		{
			cout<<"Yes"<<endl;
		}
		else cout<<"No"<<endl;

	}
	return 0;
}