1736.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1736 on 2006-07-23 at 15:37:08 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int S_MAX = 1 << 16;
const int DIR[][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

class Step {
public:
	int bx, by, ex, ey;
	void set(int, int, int, int);
	void print() const;
};
void Step::set(int cbx, int cby, int cex, int cey) {
	bx = cbx; by = cby; ex = cex; ey = cey;
}
void Step::print() const {
	printf("%d %d %d %d\n", bx+1, by+1, ex+1, ey+1);
}

int prev[S_MAX];

bool read(int&);
void find(int, int);
int move(int, int, int, int, int);

int main()
{
	int begin, end, i;
	Step step[128];

	while(read(begin) && read(end)) {
		find(begin, end);
		int sn = 0;
		for(i = end; i != begin; i = prev[i]>>5) {
			int o = prev[i]&1, x = (prev[i]>>3)&3, y = (prev[i]>>1)&3;
			step[sn++].set(x, y, x+DIR[o][0], y+DIR[o][1]);
		}
		printf("%d\n", sn);
		for(i = sn-1; i >= 0; i--) step[i].print();
	}

	return 0;
}

bool read(int& status)
{
	int i, j; char line[8];
	status = 0;
	for(i = 0; i < 4; i++) {
		if(scanf("%s", line) == EOF) return false;
		for(j = 0; j < 4; j++) status = (status<<1) | (line[j]-'0');
	}
	return true;
}
void find(int b, int e)
{
	memset(prev, -1, sizeof(prev));
	queue<int> Q;
	prev[b] = 0; Q.push(b);
	while(!Q.empty() && prev[e] == -1) {
		int i, p = Q.front(); Q.pop();
		for(i = 0; i < 32; i++) {
			int r = i>>3, c = (i>>1)&3, o = i&1, x = r+DIR[o][0], y = c+DIR[o][1];
			if(x < 0 || x >= 4 || y < 0 || y >= 4) continue;
			int now = move(p, r, c, x, y);
			if(prev[now] == -1) { prev[now] = (p<<5)|(r<<3)|(c<<1)|o; Q.push(now); }
		}
	}
}

int move(int status, int ax, int ay, int bx, int by)
{
	int ap = (3-ax)*4+(3-ay), bp = (3-bx)*4+(3-by);
	int aBit = (status>>ap)&1, bBit = (status>>bp)&1;
	status &= ~((1<<ap)|(1<<bp)); status |= (aBit<<bp) | (bBit<<ap);
	return status;
}