Untitled

 avatar
unknown
plain_text
2 years ago
1.8 kB
3
Indexable
#include<iostream>

using namespace std;

typedef struct
{
	int x,y;
}o_xy;

int T;
int N; // so hang
int M; // so quan dich
int map[205][205];

o_xy queue[1000000];
int visited[205][205];
int r = -1, f = -1;

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

void push(o_xy obj)
{
	r++;
	queue[r] = obj;
}

void pop(o_xy &obj)
{
	f++;
	obj = queue[f];
}

bool isSafe(o_xy obj)
{
	if(obj.x >= 1 && obj.x <= N && obj.y >= 1 && obj.y <= N)
		return true;
	return false;
}

void BFS(o_xy pre)
{
	r= f = -1;
	push(pre);
	visited[pre.x][pre.y] = 0;

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

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

				if(!isSafe(next) || map[next.x][next.y] == 1)	break;

				if(visited[next.x][next.y] == -1)
				{
					push(next);
					visited[next.x][next.y] = visited[pre.x][pre.y] + 1;
				}
				else if(visited[next.x][next.y] > visited[pre.x][pre.y] + 1)
				{
					visited[next.x][next.y] = visited[pre.x][pre.y] + 1;
				}
			}
		}
	}
}

void reset()
{
	r = f =-1;
	for(int i = 0; i < 205; i++)
		for(int j = 0; j < 205; j++)
			visited[i][j] = -1;

	for(int i = 0; i < 205; i++)
		for(int j = 0; j < 205; j++)
			map[i][j] = 0;

}


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

	for(int tc = 1; tc <= T; tc++)
	{
		reset();
		cin>>N>>M;
		int x_start, y_start, x_end, y_end;
		cin>>x_start>>y_start>>x_end>>y_end;
		for(int i = 0; i < M; i++)
		{
			int x,y;
			cin>>x>>y;
			map[x][y] = 1;
		}
		o_xy start;
		start.x = x_start;
		start.y = y_start;

		BFS(start);
		cout<<visited[x_end][y_end]<<endl;
	}
	return 0;
}
Editor is loading...