2935.txt

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

Problem Id:2935  User Id:fzk 
Memory:72K  Time:15MS
Language:C++  Result:Accepted

Source 

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;

#define map adfsadf
int map[100][100];

void wall( int x1, int y1, int x2, int y2 ) {
	x1*= 2, y1*=2, x2*=2, y2*=2;
	if( x1 == x2 ) {
		while( y1 <= y2 )
			map[x1][y1++] = '#';
	}
	else {
		while( x1 <= x2 )
			map[x1++][y1] = '#';
	}
}

const int dx[] = { 0, 1, -1, 0 };
const int dy[] = { 1, 0,  0,-1 };
const char to[] = "SEWN";

int bx, by, ex, ey;
queue<int> q;

void doit() {
	int x, y, i, xx, yy;
	
	bx = bx*2-1;
	by = by*2-1;
	ex = ex*2-1;
	ey = ey*2-1;
	
	wall( 0, 0, 0, 6 );
	wall( 0, 0, 6, 0 );
	wall( 6, 0, 6, 6 );
	wall( 0, 6, 6, 6 );
	
	while( !q.empty() )
		q.pop();
		
	q.push( (bx<<4) | by );
	while( 1 ) {
		x = (q.front() >> 4);
		y = ( q.front() & 15 );
		q.pop( );
		
		if( x == ex && y == ey )
			break;
			
		for( i=0; i<4; i++ )
			if( map[xx=x+dx[i]][yy=y+dy[i]] == -1 ) {
				xx += dx[i], yy += dy[i];
				if( map[xx][yy] == -1 ) {
					map[xx][yy] = 3-i;
					q.push( (xx<<4) | yy );
				}
			}
	}
	
	int k = 0;
	while( (x != bx || y !=by) && k < 100 ) {
		k++;
		printf( "%c", to[ map[x][y] ] );
		xx = x;
		x += dx[ map[x][y] ]*2;
		y += dy[ map[xx][y] ]*2;
	}
	printf( "\n" );
}

int main( ) {
	int x1, x2, y1, y2, i;
	
	while( 1 ) {
		scanf( "%d%d", &ex, &ey );
		if( ex == 0 && ey == 0 )
			break;
		scanf( "%d%d", &bx, &by );
		memset( map, -1, sizeof map );
		for( i=0; i<3; i++ ) {
			scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
			wall( x1, y1, x2, y2 );
		}
		doit( );
	}
	return 0;
}