Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.3 kB
1
Indexable
Never
#include <iostream>
using namespace std;

#define MAX_SIZE 10000000
int front = -1;
int rear = -1;
int Arx[MAX_SIZE];
int Ary[MAX_SIZE];
int Index[MAX_SIZE];

int xbgin, ybgin, xend, yend;

class queue {
public:
	bool isEmpty();
	void enqueue(int arx, int ary, int index);
	void dequeue();
	void peek(int &arx, int &ary, int &index);
};

bool queue :: isEmpty()
{
	if(front == rear)
	{
		return true;
	}
	return false;
}

void queue :: enqueue(int arx, int ary, int index)
{
	front++;
	Arx[front] = arx;
	Ary[front] = ary;
	Index[front] = index;
}

void queue :: dequeue()
{
	rear++;
}

void queue :: peek(int &arx, int &ary, int &index)
{
	arx = Arx[rear + 1];
	ary = Ary[rear + 1];
	index = Index[rear + 1];
}


int N, M;
int arr[51][51];
int ard[51][51];
void reset(int ar[51][51])
{
	for(int i = 0; i < 51; i++)
	{
		for(int j = 0; j < 51; j++)
		{
			ar[i][j] = 0; 
		}
	}
}

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

int abs(int s)
{
	int k = 0 - s;
	if(k > 0)
	{
		return k;
	}
	return s;
}

void BFS(int x1, int y1, int kc)
{
	queue qe;
	reset(ard);
	int index = 1;
	ard[x1][y1] = 1;
	qe.enqueue(x1, y1, index);
	while(!qe.isEmpty())
	{
		int x, y;
		qe.peek(x, y, index);
		qe.dequeue();
        for(int i = 1; i <= kc; i++)
		{
			for(int j = 0; j < 4; j++)
			{
				int t = x + i * dx[j];
				int k = y + dy[j];

				if(t >= 0 && t < N && k >= 0 && k < M)
				{
					if(arr[t][k] != 0 && ard[t][k] == 0)
					{
						ard[t][k] = 1;
						qe.enqueue(t, k, index);
					}
				}
			}
		}

	}
}



int main()
{
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		cin >> N >> M;
		reset(arr);
		reset(ard);
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < M; j++)
			{
				cin >> arr[i][j];
				if(arr[i][j] == 2)
				{
					xbgin = i;
					ybgin = j;
				}
				else if(arr[i][j] == 3)
				{
					xend = i;
					yend = j;
				}
			}
		}
		int ctt = 0;
		for(int i = 1; i <= N; i++)
		{
			front = rear = -1;
			BFS(xbgin, ybgin, i);
			if(ard[xend][yend] == 1)
			{
				ctt = i;
				break;
			}
		}
		
		cout<<"Case #"<<tc<<endl<<ctt<<endl;
	}
}