【搜索之BFS + 剪枝】杭电 hdu 1175 连连看

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1175
    Name  : 1175 连连看

    Date  : Thursday, April 05, 2012
    Time Stage : 2 hours

    Result:
5713239	2012-04-05 21:14:58	Accepted	1175
296MS	25372K	3624 B
C++	pyy


Test Data :

Review :
做了那么多次，终于都AC了……
之前一直以为BFS比DFS快，但是看了很多人DFS的效果，居然神奇又吐血地比我快了十倍，达到
了30几MS，而且看别人BFS的效果，也是上千MS，反正综合比起来，BFS居然比DFS还慢。
后来想到，DFS可以快速深入，而BFS则是向四面八方快速扩展。也就是说，同样是直线的距离，
假如以最快的方法，DFS用5s的时间可以到，那么BFS则是这样的，第1s，扩展一步之遥的一个格，
第2s，一步之遥的另一个格，第3s，第4s，同理……于是4s之后，DFS已经走出4步远了，
BFS还在第一步……接下来时间的差距就会越来越大了。当然这种情况对图的要求比较特别，
HDU的图貌似正好就是这样的，反正我优化后的速度都快不了……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std ;

#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value
#define max(x, y)        ((x) > (y) ? (x) : (y))
#define min(x, y)        ((x) < (y) ? (x) : (y))

#define INF     (0x3f3f3f3f)
#define MAXN    (1002)

#define DB    /##/
#define LL __int64
#define _RANGE(a, b, e)		((b) <= (a) && (a) < e)
#define _IN(nd)				(_RANGE((nd).x, 0, m) && _RANGE((nd).y, 0, n))
#define _MAP(nd)			map[(nd).y][(nd).x]
#define _PATH(nd)			path[(nd).y][(nd).x]
#define _VIS(nd)			vis[(nd).y][(nd).x]

struct NODE {
	int x, y, px, py;
	int step;
	int corn;
};

const int dir[4][2] = {0,1, 0,-1, 1,0, -1,0};

int		n, m;
bool	vis[MAXN][MAXN];
char	map[MAXN][MAXN];
NODE	beg, end, path[MAXN][MAXN];

void bfs()
{
	int i;
	queue<NODE>	q;
	NODE		t, nt;

	MEM(path, -1);
	MEM(vis, 0);

	beg.step = 0;
	beg.corn = 0;
	beg.px = beg.x;
	beg.py = beg.y;

	q.push(beg);
	while (!q.empty())
	{
		t = q.front();
		q.pop();

		for (i = 0; i < 4; ++i)
		{
			nt = t;

			if (t.corn == 2)	// 剪枝……几乎没效果
			{
				i = 4;
				if (nt.y > nt.py)
					++nt.y;
				else if (nt.y < nt.py)
					--nt.y;
				else if (nt.x > nt.px)
					++nt.x;
				else if (nt.x < nt.px)
					--nt.x;
			}
			else
			{
				nt.y += dir[i][0];
				nt.x += dir[i][1];
			}

			if (!_IN(nt) || ('0' != _MAP(nt) && _MAP(end) != _MAP(nt)))
				continue;
			/* 下一条语句是为了处理这种情况
			3 4
			1 1 1 1
			0 0 0 0
			1 1 1 1
			1
			1 1 3 3
			防止它这样走: (1,1)->..(省略号表示直线)..->(1,3)->..->(3,3)
			即是说，即使遇到相同类型的子，只要不是end指定的目标，就只能当成
			障碍跳过.
			*/
			if (_MAP(end) == _MAP(nt) && !(nt.x == end.x && nt.y == end.y))
				continue;

			if (nt.y == t.py && nt.x == t.px)	// 后退了
				continue;

			if (nt.y != t.py && nt.x != t.px)	// 转弯
			{
				nt.py = t.y;
				nt.px = t.x;
				++nt.corn;
			}
			else								// 没有转弯
			{
				nt.py = t.y;
				nt.px = t.x;
			}

			if (nt.corn >= 3 || (_VIS(nt) && nt.corn >= _PATH(nt).corn))
				continue;	// 这里不剪，貌似会超时的

DB			printf ("nt:(%d,%d)<--(%d,%d) corn:%d step:%d\n", nt.y, nt.x,	\
				nt.py, nt.px, nt.corn, nt.step);
			++nt.step;
			_PATH(nt) = nt;
			_VIS(nt) = true;
			if (nt.y == end.y && nt.x == end.x)
				return ;
			q.push(nt);
		}
	}
}

int main()
{
	int i, j, q;
	while (scanf("%d %d", &n, &m), n | m)
	{
		getchar();
		for (j = 0; j < n; ++j)
		{
			for (i = 0; i < m; ++i)
			{
				scanf("%c", &map[j][i]);
				getchar();
			}
		}
		scanf("%d", &q);
		for (i = 0; i < q; ++i)
		{
			scanf("%d %d %d %d", &beg.y, &beg.x, &end.y, &end.x);
			--beg.y; --beg.x;
			--end.y; --end.x;
			if (!_IN(beg) || !_IN(end) || _MAP(beg) != _MAP(end) || '0' == _MAP(beg))
			{
				puts("NO");
				continue;
			}
			if (beg.x == end.x && beg.y == end.y)
			{
				puts("YES");
				continue;
			}
			bfs();
			if (0 <= _PATH(end).corn && _PATH(end).corn <= 2)
				puts("YES");
			else
				printf ("NO\n");
		}
	}
	return 0;
}