1354.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1354 on 2006-06-03 at 11:51:14 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int BN = 128;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

int n, m;
bool close[BN][BN], vst[BN][BN];

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && !close[x][y]; }
bool walk(int, int, int, int);

int main()
{
	int i;
	
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		int bx, by, ex, ey; scanf("%d %d %d %d", &bx, &by, &ex, &ey);
		int cn; scanf("%d", &cn);
		memset(close, false, sizeof(close));
		for(i = 0; i < cn; i++) {
			int x, y; scanf("%d %d", &x, &y);
			close[x][y] = true;
		}
		printf("%s\n", walk(bx, by, ex, ey) ? "YES" : "NO");
	}
	
	return 0;
}

bool walk(int bx, int by, int ex, int ey)
{
	memset(vst, false, sizeof(vst));
	int stack[BN*BN], top = 0, i;
	stack[top++] = bx*BN+by; vst[bx][by] = true;
	while(top > 0 && !vst[ex][ey]) {
		int p = stack[--top], x = p >> 7, y = p & 127;
		for(i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			int bkx = ex-cx+bx, bky = ey-cy+by;
			if(!legal(cx, cy) || !legal(bkx, bky) || vst[cx][cy]) continue;
			vst[cx][cy] = true;
			if(cx == ex && cy == ey) break;
			stack[top++] = cx*BN+cy;
		}
	}
	return vst[ex][ey];
}