2435.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <queue>
using namespace std;
typedef pair<int,int> point;
int dx[] = { 0, 1,-1, 0};
int dy[] = { 1, 0, 0,-1};
char way[] = { '-','|','|','-'};
char to[] = { 'E','S','N','W'};
int n,m,bx,by,ex,ey;
bool sign[100][100];
char map[100][100];
int from[100][100];
queue<point> q;
inline bool inmap( int x, int y )
{
	return 0<=x && x<n && 0<=y && y<m;
}
void findpath()
{
	point p;
	int xx,yy,i,x,y;
	while( !q.empty() )
		q.pop();
	q.push( point(bx,by) );
	sign[bx][by] = true;
	while( !q.empty() )
	{
		p = q.front();
		q.pop();
		x = p.first, y = p.second;

		for( i=0; i<4; i++ )
		{
			if( inmap( xx=x+dx[i]*2, yy=y+dy[i]*2 ) && !sign[xx][yy] && map[x+dx[i]][y+dy[i]] == way[i] )
			{
				from[xx][yy] = 3 - i;
				sign[xx][yy] = true;
				if( xx == ex && yy == ey ) return;
				q.push( point(xx, yy) );
			}
		}
	}
		
}
void init()
{
	int i, j;
	scanf( "%d%d", &n, &m );
	n = n*2-1, m = m*2-1;

	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
	{
		scanf( "%1s", map[i]+j );
		if( map[i][j] == 'S' )
			ex = i, ey = j;
		if( map[i][j] == 'E' )
			bx = i, by = j;
	}

}
void doit()
{
	int i, s, x, y, j;

	findpath();

	x = ex, y = ey;j = -1;
	while( x != bx || y != by )
	{
		i = from[x][y];
		if( i == j ) s++;
		else
		{
			if( j != -1 ) printf( "%d\n", s );
			s = 1;
			printf( "%c ", to[i] );
			j = i;
		}
		x += dx[i]*2, y += dy[i]*2;
	}
	printf( "%d\n", s );
}
int main()
{
	init();
	doit();

	return 0;
}