[UVa] 10067 - Playing with Wheels

題目網址:  http://goo.gl/4mTQar

題 意: 有四個輪盤，每個輪盤上面有0~9的數字，所以每次能表示一個4位數字的狀態，且能透過向左或右轉動某個輪盤一次，使得狀態改變，給定一個起始狀態跟目標狀態，且限制不能到達某些狀態，問最少要轉動幾次輪盤才能達到目標，若無法則輸出 -1。


解法: 可以用BFS從起始狀態去探索，若達到目標狀態就輸出深度，若無法達到目標狀態則輸出 -1。

TAG:BFS

注意:

程式碼:

	/**
	* Tittle: 10067 - Playing with Wheels
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/15
	* File: 10067 - Playing with Wheels.cpp - solve it
	*/
	// 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) )
	class Node {
	public:
	int stt, step;
	Node( int _stt = 0, int _step = 0 ): stt(_stt), step(_step) {}
	};
	typedef queue<Node> QN;
	// declarations
	int T, n;
	int s, t;
	bool valid[100000];
	// functions
	int read4dig( void )
	{
	static int ret, tmp;
	ret = 0;
	FOR( i, 1, 4 ) {
	ret *= 10;
	scanf( "%d", &tmp );
	ret += tmp;
	}
	return ret;
	}
	int move( int stt, int dig, int type )
	{
	static int ndig, nstt;
	static char str[5];
	str[0] = (stt/1000)%10+'0';
	str[1] = (stt/100)%10+'0';
	str[2] = (stt/10)%10+'0';
	str[3] = stt%10+'0';
	ndig = str[3-dig];
	if( type == 1 ) ++ndig;
	else --ndig;
	if( ndig > '9' ) ndig = '0';
	if( ndig < '0' ) ndig = '9';
	str[3-dig] = ndig;
	sscanf( str, "%d", &nstt );
	return nstt;
	}
	int solve( void )
	{
	QN q;
	q.push( Node(s,0) );
	Node now, nxt;
	while( !q.empty() ) {
	now = q.front();
	q.pop();
	if( !valid[now.stt] ) continue;
	valid[now.stt] = false;
	if( now.stt == t ) return now.step;
	FOR( i, 0, 3 ) FOR( j, 0, 1 ) {
	nxt = Node( move(now.stt,i,j), now.step+1 );
	q.push(nxt);
	}
	}
	return -1;
	}
	// main function
	int main( void )
	{
	int tmp;
	// input
	scanf( "%d", &T );
	while( T-- ) {
	s = read4dig();
	t = read4dig();
	clr( valid, true );
	scanf( "%d", &n );
	FOR( i, 1, n ) {
	tmp = read4dig();
	valid[tmp] = false;
	}
	// solve & output
	printf( "%d\n", solve() );
	}
	return 0;
	}

view raw 10067 - Playing with Wheels.cpp hosted with ❤ by GitHub