LABYR1.cpp

#include <iostream>
using namespace std;

const int MAX = 1005;
const int MAX_QUEUE = MAX*MAX;

int C, R, T, Answer, SR, SC;
int Matrix[MAX][MAX], Mark[MAX][MAX];

typedef struct
{
	int row;
	int col;
}Point;

Point queue[MAX_QUEUE];
int fr, re, leng;

void Enqueue(int row, int col)
{
	Point p;
	p.row = row;
	p.col = col;

	queue[re] = p;
	re = (re + 1) % MAX_QUEUE;
	leng++;
}

Point Dequeue()
{
	Point p = queue[fr];
	fr = (fr + 1) % MAX_QUEUE;
	leng--;
	return p;
}

int drow[] = {-1,0,1, 0};
int dcol[] = { 0,1,0,-1};

// BFS tại điểm (row, col) tới tất cả các điểm còn lại
void BFS(int row, int col)
{
	for(int i = 0; i < R; i++)
		for(int j = 0; j < C; j++)
			Mark[i][j] = 0;

	fr = re = leng = 0;
	Enqueue(row, col);
	Mark[row][col] = 1;

	while(leng > 0)
	{
		Point p = Dequeue();
		for(int i = 0; i < 4; i++)
		{
			int r = p.row + drow[i];
			int c = p.col + dcol[i];
			if(r >= 0 && r < R && c >= 0 && c < C && 
				Mark[r][c] == 0 && Matrix[r][c] == 1)
			{
				Mark[r][c] = Mark[p.row][p.col] + 1;
				Enqueue(r,c);
			}
		}
	}
}

// Tìm điểm có khoảng cách xa nhất so với điểm xét ban đầu.
void FindMax()
{
	for(int i = 0; i < R; i++)
		for(int j = 0; j < C; j++)
			if(Mark[i][j] > Answer)
			{
				Answer = Mark[i][j];
				SR = i;
				SC = j;
			}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);

	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		Answer = SR = SC = 0;
		cin >> C >> R;
		for(int i = 0; i < R; i++)
		{
			char temp[MAX];
			cin >> temp;
			for(int j = 0; j < C; j++)
			{
				if(temp[j] == '#') Matrix[i][j] = 0;
				else if(temp[j] == '.')
				{
					Matrix[i][j] = 1;
					SR = i;
					SC = j;
				}
			}
		}

		BFS(SR,SC);
		FindMax();

		BFS(SR,SC);
		FindMax();

		cout << "Maximum rope length is " << Answer - 1 << "." << endl;
	}
	return 0;
}