1273.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1273 on 2006-07-23 at 15:35:07 */ 
#include <cstdio>

const int MAX = 7;

class Point {
public:
	int x;
	int y;
	Point(int nx = 0, int ny = 0) {
		x = nx;
		y = ny;
	}
	void operator =(const Point& p) {
		x = p.x;
		y = p.y;
	}
};

class Step {
public:
	Point begin;
	Point end;
	void init(int bx, int by, int ex, int ey) {
		begin = Point(bx+1, by+1);
		end = Point(ex+1, ey+1);
	}
	void print() {
		printf("(%d, %d) to (%d, %d)\n", begin.x, begin.y, end.x, end.y);
	}
};

class Peg {
private:
	Point last;
	int board[MAX][MAX];
	int pegN;
	bool up(int x, int y) {
		if(x < 2) {
			return false;
		} else {
			if(board[x-1][y] == 1 && board[x-2][y] == 0) {
				board[x][y] = board[x-1][y] = 0;
				board[x-2][y] = 1;
				pegN--;
				step[stepN++].init(y, x, y, x-2);
				return true;
			} else {
				return false;
			}
		}
	}
	void backUp(int x, int y) {
		board[x][y] = board[x-1][y] = 1;
		board[x-2][y] = 0;
		pegN++;
		stepN--;
	}
	bool down(int x, int y) {
		if(x >= MAX-2) {
			return false;
		} else {
			if(board[x+1][y] == 1 && board[x+2][y] == 0) {
				board[x][y] = board[x+1][y] = 0;
				board[x+2][y] = 1;
				pegN--;
				step[stepN++].init(y, x, y, x+2);
				return true;
			} else {
				return false;
			}
		}
	}
	void backDown(int x, int y) {
		board[x][y] = board[x+1][y] = 1;
		board[x+2][y] = 0;
		pegN++;
		stepN--;
	}
	bool left(int x, int y) {
		if(y < 2) {
			return false;
		} else {
			if(board[x][y-1] == 1 && board[x][y-2] == 0) {
				board[x][y] = board[x][y-1] = 0;
				board[x][y-2] = 1;
				pegN--;
				step[stepN++].init(y, x, y-2, x);
				return true;
			} else {
				return false;
			}
		}
	}
	void backLeft(int x, int y) {
		board[x][y] = board[x][y-1] = 1;
		board[x][y-2] = 0;
		pegN++;
		stepN--;
	}
	bool right(int x, int y) {
		if(y >= MAX-2) {
			return false;
		} else {
			if(board[x][y+1] == 1 && board[x][y+2] == 0) {
				board[x][y] = board[x][y+1] = 0;
				board[x][y+2] = 1;
				pegN--;
				step[stepN++].init(y, x, y+2, x);
				return true;
			} else {
				return false;
			}
		}
	}
	void backRight(int x, int y) {
		board[x][y] = board[x][y+1] = 1;
		board[x][y+2] = 0;
		pegN++;
		stepN--;
	}
	bool win() {
		int i, j;
		for(i = 0; i < MAX; i++) {
			for(j = 0; j < MAX; j++) {
				if(board[i][j] == 1) {
					if(last.x == i && last.y == j) {
						return true;
					} else {
						return false;
					}
				}
			}
		}
		return false;
	}
public:
	Step step[32];
	int stepN;
	void init() {
		int i, j, k;
		char l[64];
		stepN = pegN = 0;
		for(i = 0; i < MAX; i++) {
			while(gets(l) != NULL) {
				if(l[0] != 0) {
					break;
				}
			}
			for(j = 0, k = 0; l[j] != 0; j++) {
				switch(l[j]) {
				case 'x':
					board[i][k++] = 2;
					break;
				case 'e':
					board[i][k++] = 0;
					break;
				case 'E':
					board[i][k] = 0;
					last = Point(i, k++);
					break;
				case 'o':
					board[i][k++] = 1;
					pegN++;
					break;
				case 'O':
					board[i][k] = 1;
					last = Point(i, k++);
					pegN++;
					break;
				default:
					break;
				}
			}
		}
	}
	bool slove() {
		if(pegN == 1) {
			if(win()) {
				return true;
			} else {
				return false;
			}
		} else {
			int i, j;
			for(i = 0; i < MAX; i++) {
				for(j = 0; j < MAX; j++) {
					if(board[i][j] == 1) {
						if(up(i, j)) {
							if(slove()) {
								return true;
							} else {
								backUp(i, j);
							}
						}
						if(down(i, j)) {
							if(slove()) {
								return true;
							} else {
								backDown(i, j);
							}
						}
						if(left(i, j)) {
							if(slove()) {
								return true;
							} else {
								backLeft(i, j);
							}
						}
						if(right(i, j)) {
							if(slove()) {
								return true;
							} else {
								backRight(i, j);
							}
						}
					}
				}
			}
			return false;
		}
	}
};

int main()
{
	Peg peg;
	int T, t, i;

	scanf("%d", &T);
	getchar();
	for(t = 1; t <= T; t++) {
		if(t != 1) {
			putchar('\n');
		}
		peg.init();
		printf("Dataset %d:\n", t);
		if(!peg.slove()) {
			printf("No solution.\n");
		} else {
			for(i = 0; i < peg.stepN; i++) {
				printf("%d. ", i+1);
				peg.step[i].print();
			}
		}
	}
	
	return 0;
}