[UVa] 10102 - The path in the colored field

題目網址: http://goo.gl/9cmiJE

題 意: 給一個由 1、2、3 組成的地圖，問從地圖中的 1 走到 3 最長的最短路徑是多少。


解法: BFS找最短路，在找最大值。

TAG: BFS

注意:

程式碼:

	/**
	* Tittle: 10102 - The path in the colored field
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/21
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	class Point {
	public:
	static int m;
	int x, y;
	Point( int _x = 0, int _y = 0 ): x(_x), y(_y) {}
	const bool valid( void ) const {
	return ( 1<=x && x<=m && 1<=y && y<=m );
	}
	Point go( int dir ) {
	switch( dir ) {
	case 0: return Point(x-1,y);
	case 1: return Point(x,y+1);
	case 2: return Point(x+1,y);
	case 3: return Point(x,y-1);
	default: return Point();
	}
	}
	};
	class State {
	public:
	Point p;
	int step;
	State( Point _p = Point(), int _step = 0 ): p(_p), step(_step) {}
	};
	typedef queue<State> QS;
	// declarations
	int Point::m;
	char maze[N][N];
	bool vis[N][N];
	// functions
	int sp( const Point &s )
	{
	static Point cur, nxt;
	static int step;
	QS que;
	clr( vis, false );
	que.push( State( s, 0 ) );
	while( !que.empty() ) {
	cur = que.front().p;
	step = que.front().step;
	que.pop();
	if( vis[cur.x][cur.y] ) continue;
	vis[cur.x][cur.y] = true;
	if( maze[cur.x][cur.y] == '3' )
	return step;
	FOR( i, 0, 3 ) if( cur.go(i).valid() ) {
	nxt = cur.go(i);
	que.push( State(nxt,step+1) );
	}
	}
	return -1;
	}
	// main function
	int main( void )
	{
	int maxp;
	// input
	while( scanf( "%d", &Point::m ) == 1 ) {
	FOR( i, 1, Point::m )
	scanf( "%s", maze[i]+1 );
	// solve
	maxp = 0;
	FOR( i, 1, Point::m ) FOR( j, 1, Point::m ) if( maze[i][j] == '1' )
	maxp = max( maxp, sp( Point(i,j) ) );
	// output
	printf( "%d\n", maxp );
	}
	return 0;
	}

view raw 10102 - The path in the colored field.cpp hosted with ❤ by GitHub