Untitled

 avatar
unknown
plain_text
2 years ago
1.3 kB
3
Indexable
#include<iostream>
using namespace std;
int M,N, h;
int A[55][55];
int visit[55][55];
int x_st, y_st, x_end , y_end;
int f=-1;
int Qx[100000];
int Qy[100000];
int dx[4]= {1,-1,0,0};
int dy[4]= {0,0,1,-1};
void push(int x,int y)
{
	f++;
	Qx[f] =x;
	Qy[f] =y;
}
void reset()
{
	for(int i=1; i<= M; i++)
	{
		for(int j=1; j<=N; j++)
		{
			visit[i][j] =0;
		}
	}
}
void pop(int &x,int &y)
{
	x= Qx[f];
	y= Qy[f];
	f--;
}
bool dfs(int x,int y,int h)
{
	f=-1;
	push(x,y);
	visit[x][y] =1;
	while(f != -1)
	{
		pop(x,y);
		for(int i=1; i<=h; i++)
		{
			for(int j=0; j<4; j++)
			{
				int xx = x +i* dx[j];
				int yy= y + dy[j];
				if(visit[xx][yy] == 0 && xx>=1 && xx <=M && yy >=1 && yy <=N && A[xx][yy] != 0){
					if(A[xx][yy] == 3) { return true; }
					push(xx,yy);
					visit[xx][yy] =1;
				}
			}
		}
	}
	return false;
}
int main()
{
	int t;
	cin >> t;
	for(int stt=1; stt <=t; stt++)
	{
		cin >> M >> N;
		for(int i=1; i<= M; i++)
		{
			for(int j=1; j<=N; j++)
			{
				cin >> A[i][j];
				if(A[i][j] ==2) { x_st = i; y_st = j;}
			}
		}
		//////////////////////////
		int ans =0;
		for(int i=1; i<= N-1; i++){
			reset();
			if(dfs(x_st,y_st,i)){
				ans = i;
				break;
			}
		}
		///////////////////
		cout << "Case #" << stt << endl << ans << endl;
	}
}
Editor is loading...