pku2056.cpp

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

#include <stdio.h>
#include <string.h>
#define size 210

typedef struct Node
{
	int x, y, p;
} Node;

Node q[size * size];
int N, M;
char Mp[size][size];
int vis[size][size];
int Dis[3][2] = {0, 1, 0, -1, 1, 0};
int hd, tl;

int In(int x, int y)
{
	return y > 0 && y < M - 1 && x < N;
}

int main()
{
	int i, j, nx, ny, x, y, p;
	while (scanf("%d %d", &N, &M) != -1 && (M + N))
	{
		memset(Mp, 0, sizeof(Mp));
		for (i = 0; i < N; i++)
		{
			for (j = 0; j < M; j++)
			{
				while (1)
				{
					scanf("%c", &Mp[i][j]);
					if (Mp[i][j] == 'W' || Mp[i][j] == 'S' || Mp[i][j] == 'B')
					{
						break;
					}
				}
			}
			for (j = M - 1; j > 0; j--)
			{
				if (Mp[i][j - 1] == 'S')
				{
					Mp[i][j] = 'S';
					break;
				}
			}
		}
		memset(vis, 0, sizeof(vis));
		hd = 0;
		tl = 0;
		
		for (i = 0; i < N; i += N - 1)
		{
			Mp[i][0] = 'W';
			Mp[i][M - 1] = 'B';
		}
		
		for (i = 0; i < M; i++)
		{
			if (Mp[0][i] == 'S')
			{
				q[tl].x = 0;
				q[tl].y = i;
				q[tl].p = 1;
				vis[0][i] = 1;
				tl++;
			}
		}
		while (hd < tl)
		{
			x = q[hd].x;
			y = q[hd].y;
			p = q[hd].p;
			for (i = 0; i < 3; i++)
			{
				nx = x + Dis[i][0];
				ny = y + Dis[i][1];
				if (In(nx, ny) && !vis[nx][ny] && Mp[nx][ny] == 'S')
				{
					q[tl].x = nx;
					q[tl].y = ny;
					q[tl].p = p + 1;
					vis[nx][ny] = p + 1;
					tl++;
				}
			}
			hd++;
			if (q[hd].x == N - 1)
			{
				printf("%d\n", q[hd].p);
				break;
			}
		}
	}
	return 0;
}