1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include <stdlib.h>
#include <string.h>
#define SIZE 1000000
const int INF = 999999;
typedef struct
{
int x;
int y;
int dir;
int num;
}point;
struct
{
point base[SIZE];
int front,rear;
}Q;
void init() {Q.rear = Q.front = 0;}
void Push(point e)
{
Q.base[Q.rear].x = e.x;
Q.base[Q.rear].y = e.y;
Q.base[Q.rear].dir = e.dir;
Q.base[Q.rear].num = e.num;
Q.rear = (Q.rear+1)%SIZE;
}
point Pop()
{
point e;
e.x = Q.base[Q.front].x;
e.y = Q.base[Q.front].y;
e.dir = Q.base[Q.front].dir;
e.num = Q.base[Q.front].num;
Q.front = (Q.front+1)%SIZE;
return e;
}
int n,m,q;
int map[1010][1010];
int mark[1010][1010];
int iPlus[4] = {-1,0,1,0};
int jPlus[4] = {0,-1,0,1};
void BFS(point p1,point p2)
{
int k;
point next,pre;
init();
pre.x = p1.x;pre.y = p1.y;
pre.num = 0;
pre.dir = -1;
Push(pre);
mark[p1.x][p1.y] = 0;
while (Q.rear!=Q.front)
{
pre = Pop();
for ( k = 0; k < 4; k++)
{
next.x = pre.x + iPlus[k];
next.y = pre.y + jPlus[k];
if (next.x < 1 || next.y < 1 || next.x > n || next.y > m)
continue;
if (pre.dir == -1 )
next.num = 0;
else
{
if ( k != pre.dir )
next.num = pre.num + 1;
else
next.num = pre.num;
}
next.dir = k;
if ( next.x == p2.x && next.y==p2.y && next.num <= 2 )
{
printf("YESn");
return;
}
if ( map[next.x][next.y] == 0 && next.num <= mark[next.x][next.y] )
{
mark[next.x][next.y] = next.num;
Push(next);
}
}
}
printf("NOn");
}
int main()
{
freopen("Sample Input.txt","r",stdin);
system("Color F0");
int i,j,k;
point p1,p2;
while ( scanf("%d%d",&n,&m),n&&m)
{
for ( i = 1; i <= n; i++)
for ( j = 1; j <= m; j++)
scanf("%d",&map[i][j]);
scanf("%d",&q);
while (q--)
{
scanf("%d%d%d%d",&p1.x,&p1.y,&p2.x,&p2.y);
for ( i = 1; i <= n; i++)
for ( j = 1; j <= m ; j++)
mark[i][j] = INF;
if (map[p1.x][p1.y]==0 || map[p2.x][p2.y]==0 || map[p1.x][p1.y] != map[p2.x][p2.y] )
{
printf("NOn");
continue;
}
if (p1.x < 1 || p1.y < 1 || p1.x > n || p1.y > m || p2.x < 1 || p2.y < 1 || p2.x > n || p2.y > m)
{
printf("NOn");
continue;
}
BFS(p1,p2);
}
}
getch();
return 0;
}
|
近期评论