-
Notifications
You must be signed in to change notification settings - Fork 0
/
10653.cpp
79 lines (63 loc) · 1.9 KB
/
10653.cpp
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
#include<bits/stdc++.h>
#define N 1000000
#define INF 10000000
using namespace std;
int matrix [1000 + 5] [1000 + 5];
int R, C;
queue <int> q;
void reset ()
{
for ( int i = 0; i < 1005; i++ )
memset (matrix [i], -1, sizeof (matrix [i]));
}
bool valid (int r, int c)
{
if ( r >= 0 && r <= R && c >= 0 && c <= C ) return true;
return false;
}
void insert (int r, int c, int val)
{
matrix [r] [c] = val + 1;
q.push (r);
q.push (c);
}
int main ()
{
while ( scanf ("%d %d", &R, &C) ) {
if ( R == 0 && C == 0 ) break;
reset ();
int r;
scanf ("%d", &r);
for ( int i = 0; i < r; i++ ) {
int rowNumber;
scanf ("%d", &rowNumber);
int mines;
scanf ("%d", &mines);
for ( int j = 0; j < mines; j++ ) {
int pos;
scanf ("%d", &pos);
matrix [rowNumber] [pos] = INF;
}
}
int sourceR, sourceC, destR, destC;
scanf ("%d %d %d %d", &sourceR, &sourceC, &destR, &destC);
matrix [sourceR] [sourceC] = 0;
q.push (sourceR);
q.push (sourceC);
while ( !q.empty() ) {
int row, col;
row = q.front (); q.pop ();
col = q.front (); q.pop ();
if ( valid (row - 1, col ) && matrix [row - 1] [col] < 0 )
insert (row - 1, col, matrix [row] [col]);
if ( valid (row, col + 1) && matrix [row] [col + 1] < 0 )
insert (row, col + 1, matrix [row] [col]);
if ( valid (row + 1, col) && matrix [row + 1] [col] < 0 )
insert (row + 1, col, matrix [row] [col]);
if ( valid (row, col - 1) && matrix [row] [col - 1] < 0 )
insert (row, col - 1, matrix [row] [col]);
}
printf ("%d\n", matrix [destR] [destC]);
}
return 0;
}