pku1383.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define SIZ 1001

typedef struct 
{
	int x, y, dis;
} Poi;

Poi q[SIZ * SIZ];
int head, tail, R, C;
char map[SIZ][SIZ];
int st[SIZ][SIZ];
int D[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int can(int x, int y)
{
	if (x >= R || x < 0 || y >= C || y < 0 || map[x][y] != '.' || st[x][y] == 1)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

int BFS(Poi sta)
{
	int i, j;
	Poi tmp;
	int dis, nextx, nexty;
	for (i = 0; i < R; i++)
	{
		for (j = 0; j < C; j++)
		{
			st[i][j] = 0;
		}
	}
	head = 0;
	tail = 0;
	q[0] = sta;
	q[0].dis = 0;
	st[sta.x][sta.y] = 1;

	do
	{
		dis = q[head].dis + 1;
		for (i = 0; i < 4; i++)
		{
			nextx = q[head].x + D[i][0];
			nexty = q[head].y + D[i][1];
			if (can(nextx, nexty))
			{
				tail++;
				q[tail].x = nextx;
				q[tail].y = nexty;
				q[tail].dis = dis;
				st[nextx][nexty] = 1;
			}
		}
		head++;
	}
	while (head <= tail);
	return dis - 1;
}

int main()
{
	int T, i, j, l;
	Poi start;
	scanf("%d", &T);
	
	while (T--)
	{
		scanf("%d%d", &C, &R);

		for (i = 0; i < R; i++)
		{
			scanf("%s", map[i]);
		}

		for (i = 0; i < R; i++)
		{
			for (j = 0; j < C; j++)
			{
				if (map[i][j] == '.')
				{
					start.x = i;
					start.y = j;
					i = R;
					j = C;
					break;
				}
			}
		}

		l = BFS(start);
		l = BFS(q[head - 1]);
		printf("Maximum rope length is %d.\n", l);
	}
	return 0;
}