[World Final 1995][POJ] 1878 Jill's Bike

題目網址: http://poj.org/problem?id=1878

題意: 給一個2維的方格地圖、道路方向(單向)以及每個點的高度，若相鄰兩點有道路且目標高度不超過10，即可以走，求兩點間的最短距離。



解法: just BFS。

TAG: SPFA, DP

注意: BFS

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	struct Node {
	int x, y;
	Node ( int _x = 0, int _y = 0 ): x(_x), y(_y) {}
	Node u( void ) { return Node(x+1,y); }
	Node d( void ) { return Node(x-1,y); }
	Node l( void ) { return Node(x,y-1); }
	Node r( void ) { return Node(x,y+1); }
	const bool operator==( const Node &op ) const { return (x==op.x && y==op.y); }
	};
	typedef queue<Node> QN;
	int att[25][25];
	bool e[25][25][25][25];
	Node path[25][25];
	bool vis[25][25];
	Node p1, p2;
	int r, c;
	bool valid( const Node &p )
	{
	return ( p.x >= 1 && p.x <= r && p.y >= 1 && p.y <= c );
	}
	bool bfs( const Node &s, const Node &t )
	{
	static Node now, np;
	static QN q;
	memset( vis, false, sizeof(vis) );
	memset( path, 0, sizeof(path) );
	while( !q.empty() ) q.pop();
	now = s;
	q.push(now);
	vis[now.x][now.y] = true;
	while( !q.empty() ) {
	now = q.front(); q.pop();
	if( now == t ) {
	return true;
	}
	np = now.u();
	if( valid(np) && !vis[np.x][np.y] && e[now.x][now.y][np.x][np.y] ) {
	q.push(np); path[np.x][np.y] = now; vis[np.x][np.y] = true;
	}
	np = now.d();
	if( valid(np) && !vis[np.x][np.y] && e[now.x][now.y][np.x][np.y] ) {
	q.push(np); path[np.x][np.y] = now; vis[np.x][np.y] = true;
	}
	np = now.l();
	if( valid(np) && !vis[np.x][np.y] && e[now.x][now.y][np.x][np.y] ) {
	q.push(np); path[np.x][np.y] = now; vis[np.x][np.y] = true;
	}
	np = now.r();
	if( valid(np) && !vis[np.x][np.y] && e[now.x][now.y][np.x][np.y] ) {
	q.push(np); path[np.x][np.y] = now; vis[np.x][np.y] = true;
	}
	}
	return false;
	}
	void pPath( const Node s, const Node t )
	{
	if( t == s ) {
	printf( "%d-%d", s.x, s.y );
	} else {
	pPath( s, path[t.x][t.y] );
	printf( " to %d-%d", t.x, t.y );
	}
	}
	int main( void )
	{
	int i, j;
	int step;
	while( scanf( "%d%d", &r, &c ) == 2 ) {
	memset( e, false, sizeof(e) );
	for( i = 1; i <= r; ++i ) for( j = 1; j <= c; ++j ) scanf( "%d", &att[i][j] );
	while( scanf( "%d%d%d%d", &p1.x, &p1.y, &p2.x, &p2.y ) == 4 && (p1.x||p1.y||p2.x||p2.y) ) {
	if( p1.x == p2.x ) {
	if( p1.y < p2.y ) {
	for( i = p1.y; i < p2.y; ++i ) if( att[p1.x][i]+10 >= att[p2.x][i+1] )
	e[p1.x][i][p2.x][i+1] = true;
	}
	else {
	for( i = p1.y; i > p2.y; --i ) if( att[p1.x][i]+10 >= att[p2.x][i-1] )
	e[p1.x][i][p2.x][i-1] = true;
	}
	} else {
	if( p1.x < p2.x ) {
	for( i = p1.x; i < p2.x; ++i ) if( att[i][p1.y]+10 >= att[i+1][p2.y] )
	e[i][p1.y][i+1][p2.y] = true;
	}
	else {
	for( i = p1.x; i > p2.x; --i ) if( att[i][p1.y]+10 >= att[i-1][p2.y] )
	e[i][p1.y][i-1][p2.y] = true;
	}
	}
	}
	while( scanf( "%d%d%d%d", &p1.x, &p1.y, &p2.x, &p2.y ) == 4 && (p1.x||p1.y||p2.x||p2.y) ) {
	if( p1 == p2 ) {
	printf( "To get from %d-%d to %d-%d, stay put!\n", p1.x, p1.y, p2.x, p2.y );
	} else {
	if( bfs( p1, p2 ) ) {
	pPath( p1, p2 );
	putchar('\n');
	} else {
	printf( "There is no acceptable route from %d-%d to %d-%d.\n", p1.x, p1.y, p2.x, p2.y );
	}
	}
	putchar('\n');
	}
	}
	return 0;
	}

view raw Jill's Bike.cpp hosted with ❤ by GitHub