Untitled

 avatar
unknown
plain_text
2 years ago
1.4 kB
3
Indexable
#include<iostream>
using namespace std;

int n,m;
int map[101][101];
int vs[101][101] = {0};
int Qx[10000000], Qy[1000000], Qd[10000000];
int front =-1, rear = -1;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int start_x, start_y;
int t;

bool checkbien(int x, int y)
{
	if ( x <0 || x >=m || y < 0 || y >=n) return false;
	return true;
}


void push(int x, int y, int d)
{
	rear ++;
	Qx[rear] = x;
	Qy[rear] = y;
	Qd[rear] = d;
}

void pop(int &x, int &y, int &d)
{
	front ++;
	x = Qx[front];
	y = Qy[front];
	d = Qd[front];
}


int Bfs(int x, int y, int d)
{
	int max = 0;
	int xx, yy;
	push(x,y,d);
	while (front != rear)
	{
		pop (x,y,d);
		for (int i=0; i<4; i++)
		{
			 xx = x + dx[i];
			 yy = y + dy[i];
			if (checkbien(xx,yy) && map[xx][yy] == 1 && vs[xx][yy] == 0)
			{
				push(xx,yy,d+1);
				vs[xx][yy] = d+1;
				if (max < vs[xx][yy]) max = vs[xx][yy];
			}
		}
	}
	return max;
}


int main()
{

	cin >> t;

	
	for (int tc =1; tc <= t; tc++){
		cin >> n >> m;
		front = rear = -1;
		for (int i=0; i<m; i++)
			for (int j=0; j<n; j++)
				cin >> map[i][j];

		for (int i=0; i<m; i++)
			for (int j=0; j<n; j++)
				vs[i][j] = 0;

		cin >> start_y >> start_x;
		vs[start_x-1][start_y-1] = 1;
		cout << Bfs(start_x-1,start_y-1,1)<<endl;
	}

	return 0;
}
Editor is loading...