[UVa] 10259 - Hippity Hopscotch

題目網址: https://goo.gl/3WbIJ1

題意:
(from luckycat)


解法:
我覺得是 最短路徑的變形...
但是查到的方法都是DP...  雖然 SPFA 也算DP
總之我用 SPFA 解。

TAG: DP, SPFA,

注意:

程式碼:

	/**
	* Tittle: 10259 - Hippity Hopscotch
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/29
	*/
	// 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
	struct Point {
	int x, y;
	Point( int _x=0, int _y=0 ): x(_x), y(_y) {}
	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);
	}
	}
	};
	typedef queue<Point> QP;
	// declarations
	int t;
	int n , k;
	int penny[N][N];
	int d[N][N];
	// functions
	inline const bool valid( const Point &p )
	{
	return (0<=p.x && p.x<n && 0<=p.y & p.y<n);
	}
	void spfa( void )
	{
	static Point cur, nxt;
	static bool inQ[N][N];
	static int cnt;
	clr( d, 0 );
	clr( inQ, false );
	d[0][0] = penny[0][0];
	QP que;
	que.push( Point(0,0) );
	inQ[0][0] = true;
	while( !que.empty() ) {
	cur = que.front();
	que.pop();
	inQ[cur.x][cur.y] = false;
	FOR( dir, 0, 3 ) {
	nxt = cur;
	cnt = k;
	while( cnt-- ) {
	nxt = nxt.go(dir);
	if( !valid(nxt) ) break;
	if( penny[cur.x][cur.y]>=penny[nxt.x][nxt.y] ) continue;
	if( d[cur.x][cur.y]+penny[nxt.x][nxt.y]>d[nxt.x][nxt.y] ) {
	d[nxt.x][nxt.y] = d[cur.x][cur.y]+penny[nxt.x][nxt.y];
	if( !inQ[nxt.x][nxt.y] ) {
	que.push( nxt );
	inQ[nxt.x][nxt.y] = true;
	}
	}
	}
	}
	}
	}
	// main function
	int main( void )
	{
	int ans;
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d%d", &n, &k );
	FOR( i, 0, n-1 ) FOR( j, 0, n-1 )
	scanf( "%d", &penny[i][j] );
	// solve
	spfa();
	// output
	ans = 0;
	FOR( i, 0, n-1 ) FOR( j, 0, n-1 )
	ans = max( ans, d[i][j] );
	printf( "%d\n", ans );
	if( t ) putchar('\n');
	}
	return 0;
	}

view raw 10259 - Hippity Hopscotch.cpp hosted with ❤ by GitHub