1. #include <set>
2. #include <iostream>
3. #include <vector>
4. #include <algorithm>
5. #include <stdlib.h>
6. #include <math.h>
7. #include <string.h>
8. #include <queue>
9. using namespace std;
12. #define MAX 300
15. int map[MAX][MAX];
16. bool visit[MAX][MAX]; // 访问标记
17. int dir[4][2] = {
    0, 1, 0, -1, 1, 0, -1, 0}; // 方向向量 右，左，下，上
18. int num;
21. struct data // BFS队列中的状态数据结构
22. {
23. int x, y; // 坐标位置
24. int step; // 搜索步数统计器
25. int state;
26. }start, over;
30. void input_bfs(int row, int column)
31. {
32. int flag =0;
33. int state;
34. for(int i=1; i<=row; i++)
35. for(int j=1; j<=column; j++)
36. {
37. scanf("%d", &state);
39. if(state == 2)
40. {
    start.x = i; start.y = j; start.state = 2;}
41. else if(state == 3)
42. {
    over.x = i; over.y =j; over.state = 3;}
44. map[i][j] = state;
45. }
46. }
48. void initialize(int row, int column)
49. {
50. memset(map, 0, sizeof(map) );
51. memset(visit, false, sizeof(visit) );
52. for(int i=1; i<=row; i++)
53. for(int j=1; j<=column; j++)
54. visit[i][j] = true;
55. num = 0;
56. }
60. bool check_bfs(data temp)
61. {
62. if(visit[temp.x][temp.y] && map[temp.x][temp.y] ) // 满足条件，根据条件添加
63. return 1;
64. else return 0;
65. }
69. void bfs(data first)
70. {
71. queue<data> que; // BFS队列
72. data now, next; // 定义2个状态，当前和下一个
73. first.step = 0; // 计数器清零
75. int begin = 0;
76. que.push(first);
77. visit[first.x][first.y] = 0;
79. while(!que.empty() )
80. {
81. now = que.front(); // 取队首元素进行扩展
82. if(now.step !=begin) {
    begin = now.step; num++;}
83. if(now.x == over.x && now.y == over.y) // 出现目标态，此时为Step的最小值，可以退出即可
84. {
85. over.step = now.step; // 做相关处理
86. return ;
87. }
89. if(map[now.x][now.y] == 4 && now.step < 6)
90. now.step = 0;
92. for(int i=0; i<4; i++)
93. {
95. next.x = now.x + dir[i][0];
96. next.y = now.y + dir[i][1];
97. next.step = now.step +1;
99. if(check_bfs(next) ) // 如果状态满足约束条件则入队
100. {
101. que.push(next);
102. visit[next.x][next.y] = 0;
103. }
104. }
105. que.pop(); // 队首元素出队
106. }
108. return ;
109. }
111. int main()
112. {
113. freopen("read.txt", "r", stdin);
114. int T;
115. scanf("%d", &T);
116. while(T--)
117. {
118. int row, column;
119. scanf("%d%d", &row, &column);
121. initialize(row, column);
122. input_bfs(row, column);
124. bfs(start);
126. if(over.step < 6)
127. printf("%d\n", num);
128. else printf("-1\n");
129. }
131. return 0;
132. }

    

附件列表