3371548_ac_16ms_752k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node
{
	int x, y;
};

queue <node> que;
char map[301][301];
int n, m;
int sti, stj;
int edi, edj;
int cost[301][301];
const int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

bool valid(int x,int y)
{
	return x >= 0 && y >= 0 && x < n && y < m;
}

void bfs()
{
	node t, q;
	int i, x, y;

	while (!que.empty())
	{
		que.pop();
	}
	memset(cost, -1, sizeof(cost));
	t.x = sti;t.y = stj;
	que.push(t);
	cost[sti][stj] = 0;
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		for(i = 0; i < 4; i++)
		{
			x = t.x + mov[i][0];
			y = t.y + mov[i][1];
			if(valid(x,y)&&map[x][y]!='#'&&(cost[x][y]==-1||cost[x][y]>cost[t.x][t.y]+1+(map[x][y]=='X')))
			{
				cost[x][y] = cost[t.x][t.y]+1+(map[x][y]=='X');
				q.x = x;
				q.y = y;
				que.push(q);
			}
		}
	}
	printf("%d\n",cost[edi][edj]);
}

int main()
{
	int i;
	char *p;

	while (scanf("%d%d", &n, &m)==2)
	{
		if (m == 0 && n == 0)
		{
			break;
		}
		for (i = 0; i < n; i++)
		{
			scanf("%s", map[i]);
			for (int j = 0; map[i][j]; j++)
			{
				if (map[i][j] == 'S' || map[i][j] == 'R')
				{
					map[i][j] = '#';
				}
				else
				{
					if (map[i][j] == 'B')
					{
						map[i][j] = 'X';
					}
				}
			}
			if ((p = strchr(map[i], 'Y')) != NULL)
			{
				sti = i;
				stj = p - map[i];
			}
			if ((p = strchr(map[i], 'T')) != NULL)
			{
				edi = i;
				edj = p - map[i];
			}
		}
		bfs();
	}
	return 0;
}