bfs+记录路径。记录路径是可以通过记录此点的前驱，最后通过递归实现路径的输出。

//2212211	2010-03-19 19:41:45	Accepted	1026	78MS	684K	2243 B	C++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

const int N = 105;

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

typedef struct
{
	int x, y;
	int cost;
	int prex, prey;
}Node;

char G[N][N];
Node path[N][N];
int n, m;

bool isBound(int x, int y)
{
	if(x < 0 || x >= n)
		return false;
	if(y < 0 || y >= m)
		return false;
	return true;
}

void bfs()
{
	queue<Node> Q;
	Node a, b;
	int i;
	int xx;

	a.x = 0; a.y = 0; a.cost = 0;
	a.prex = 0; a.prey = 0;
	if(G[0][0] != '.')
		a.cost = G[0][0] - '0';
	path[0][0] = a;
	
	Q.push(a);
	while(!Q.empty())
	{
		a = Q.front();
		Q.pop();
		for(i = 0; i < 4; i++)
		{
			b.x = a.x + dir[i][0];
			b.y = a.y + dir[i][1];
			if(isBound(b.x, b.y) && G[b.x][b.y] != 'X')
			{
				if(G[b.x][b.y] == '.')
					b.cost = a.cost + 1;
				else
					b.cost = a.cost + G[b.x][b.y] - '0' + 1;
				if(path[b.x][b.y].cost == -1 || path[b.x][b.y].cost > b.cost)
				{
					b.prex = a.x; b.prey = a.y;
					path[b.x][b.y] = b;
					Q.push(b);
				}
			}
		}

	}
	if(path[n - 1][m - 1].cost == -1)
	{
		cout<<"God please help our poor hero."<<endl;
		cout<<"FINISH"<<endl;
	}else
	{
		cout<<"It takes "<<path[n - 1][m - 1].cost<<" seconds to reach the target position, let me show you the way."<<endl;
		stack<Node> S;
		a = path[n - 1][m - 1];
		//S.push(a);
		while(1)
		{
			if(a.x == 0 && a.y == 0)
				break;
			S.push(a);
			a = path[a.prex][a.prey];
		}
		a = path[0][0];

		xx = 1;
		while(!S.empty())
		{
			b = S.top();
			S.pop();
			if(G[b.x][b.y] == '.')
			{
				cout<<xx++<<"s:("<<a.x<<","<<a.y<<")->("<<b.x<<","<<b.y<<")"<<endl;
			}else
			{
				cout<<xx++<<"s:("<<a.x<<","<<a.y<<")->("<<b.x<<","<<b.y<<")"<<endl;
				i = G[b.x][b.y] - '0';
				while(i--)
				{
					cout<<xx++<<"s:FIGHT AT ("<<b.x<<","<<b.y<<")"<<endl;
				}
			}
			a = b;
		}
		cout<<"FINISH"<<endl;
	}
}

int main()
{
	int i, j;
	while(cin>>n>>m)//The input is terminated by the end of file
	{
		for(i = 0; i < n; i++)
			cin>>G[i];
		for(i = 0; i < n; i++)
			for(j = 0; j < m; j++)
				path[i][j].cost = -1;
		bfs();
	}
	return 0;
}

• 相关文章
• 全局相关文章