Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.7 kB
0
Indexable
Never
#include<iostream>

using namespace std;

int N, M;
int map[55][55];
int x_start, y_start, x_gold, y_gold;

bool visited[55][55];

int Qx[10000];
int Qy[10000];

int r = -1, f = -1;

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

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

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

bool isSafe(int x, int y)
{
	if(x >= 0 && x < N && y >= 0 && y < M)
		return true;
	return false;
}

bool BFS(int x, int y, int step)
{
	push(x,y);
	visited[x][y] = true;

	while(r != f)
	{
		pop(x,y);

		for(int i =0; i< 4; i++)
		{

			for(int j = 1; j <= step; j++)
			{
				int xx, yy;
				xx = x + j*dx[i];
				yy = y + dy[i];

				if(isSafe(xx,yy) && map[xx][yy] == 1 && visited[xx][yy] == false)
				{
					push(xx,yy);
					visited[xx][yy] = true;
				}
				if(isSafe(xx,yy) && map[xx][yy] == 3)
				{
					return true;
				}
			}
		}
	}
	return false;
}

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


int main()
{
	//freopen("Text.txt", "r", stdin);
	int T;
	cin>>T;
	for(int tc = 1; tc <= T; tc++)
	{
		cin>>N>>M;
		int ans = 0;
		reset();
		for(int i = 0; i< N; i++)
			for(int j =0; j < M; j++)
			{
				cin>>map[i][j];
				if(map[i][j] == 2)
				{
					x_start = i;
					y_start = j;
				}
			}

			for(int step = 1; step <= N -1; step++)
			{
				reset();
				if(BFS(x_start,y_start,step))
				{
					ans = step;
					break;
				}
			}
			cout<<"Case #"<<tc<<endl;
			cout<<ans<<endl;
	}
	return 0;
}