【検索の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
", 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
");
		}
	}
	return 0;
}