1struct Point
2{
3 int x;
4 int y;
5};
6
7struct queueNode
8{
9 Point pt;
10 int dist;
11};
12
13bool isValid(int row, int col)
14{
15 return (row >= 0) && (row < ROW) &&
16 (col >= 0) && (col < COL);
17}
18
19int rowNum[] = {-1, 0, 0, 1};
20int colNum[] = {0, -1, 1, 0};
21
22int Lee(int mat[][COL], Point src, Point dest)
23{
24 if (!mat[src.x][src.y] || !mat[dest.x][dest.y])
25 return -1;
26
27 bool visited[ROW][COL];
28 memset(visited, false, sizeof visited);
29
30 visited[src.x][src.y] = true;
31
32 queue<queueNode> q;
33
34
35 queueNode s = {src, 0};
36 q.push(s);
37
38 while (!q.empty())
39 {
40 queueNode curr = q.front();
41 Point pt = curr.pt;
42
43 if (pt.x == dest.x && pt.y == dest.y)
44 return curr.dist;
45
46 q.pop();
47
48 for (int i = 0; i < 4; i++)
49 {
50 int row = pt.x + rowNum[i];
51 int col = pt.y + colNum[i];
52
53 if (isValid(row, col) && mat[row][col] &&
54 !visited[row][col])
55 {
56 visited[row][col] = true;
57 queueNode Adjcell = { {row, col},
58 curr.dist + 1 };
59 q.push(Adjcell);
60 }
61 }
62 }
63
64 return -1;
65}
66
