2157.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2157 on 2006-01-28 at 12:27:03 */ 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int S_MAX = 32768;
const char *KEYBOARD[] = { "789", "456", "123", "00x" };
typedef pair<int, int> pii;

class Point {
public:
	int x, y;
	void set(int, int);
	inline bool legal() const;
};
void Point::set(int cx, int cy) {
	x = cx; y = cy;
}
inline bool Point::legal() const {
	return (x >= 0 && x < 4 && y >= 0 && y < 3 && isdigit(KEYBOARD[x][y]));
}

const Point DIR[] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { 0, 0 } };
char type[MAX];
bool vst[S_MAX];
queue<pii> Q;

inline void push(const Point&, const Point&, int, int);

int main()
{
	int i, j;
	
	while(strcmp(gets(type), "eof")) {
		memset(vst, false, sizeof(vst));
		while(!Q.empty()) Q.pop();
		Point left = { 1, 0 }, right = { 1, 1 };
		push(left, right, 0, 0);
		int move = -1;
		while(!Q.empty() && move == -1) {
			pii t = Q.front(); Q.pop();
			int c[5], m;
			for(i = 0; i < 4; i++, t.first >>= 2) c[i] = (t.first & 3);
			c[4] = t.first;
			left.set(c[0], c[1]); right.set(c[2], c[3]);
			for(i = 0; i < 5 && move == -1; i++)
				for(j = 0; j < 5; j++) {
					Point cl = { left.x+DIR[i].x, left.y+DIR[i].y }, cr = { right.x+DIR[j].x, right.y+DIR[j].y };
					if(cl.legal() && cr.legal()) {
						int step = c[4];
						if(i == 4 && KEYBOARD[cl.x][cl.y] == type[c[4]]) step++;
						else if(j == 4 && KEYBOARD[cr.x][cr.y] == type[c[4]]) step++;
						if(type[step] == 0) { move = t.second+1; break; }
						else push(cl, cr, step, t.second+1);
						m = Q.size();
					}
				}
		}
		printf("%d\n", move);
	}
	
	return 0;
}

inline void push(const Point& l, const Point& r, int tn, int mn)
{
	if(l.y >= r.y) return;
	int status = l.x | (l.y<<2) | (r.x<<4) | (r.y<<6) | (tn<<8);
	if(!vst[status]) Q.push(pii(status, mn));
	vst[status] = true;
}