判断迷宫中两点是否连通，我老是过不了，大佬救命

chenlifeng

题目网址  迷宫
我的代码

1. #include<cstdio>
   
2. #define  MAX 100
   
3. #include<iostream>
   
4. using namespace std;
   
5. 
   
6. int map[MAX][MAX]{};                        //迷宫与起点连通部分
   
7. char maze[MAX][MAX]{};                        //存放迷宫
   
8. bool visit[MAX][MAX]{};                        //记录已经访问的结点
   
9. int xstep[4] = {0,1,0,-1};                //从一个点的四个方向
   
10. int ystep[4] = {1,0,-1,0};
    
11. int num;                                                //迷宫边长
    
12. 
    
13. void init(int n);                                                //初始化
    
14. bool find_map(int x, int y, int num);        //返回map[x][y]
    
15. void in_maze(int n);                                        //输入迷宫，从键盘
    
16. int validate(int x, int y, int num);        //(x,y)没越界则返回true
    
17. void our_map(int num);                                        //输出
    
18. void search(int x,int y);                                //递归深度优先搜索
    
19. 
    
20. int main() {
    
21.         int times;
    
22.         scanf("%d", &times);
    
23.         for(int t = 0; t < times; t++) {
    
24.                
    
25.         int start[2]{}, end[2]{};
    
26.         scanf("%d", &num);
    
27.         in_maze(num);
    
28.         scanf("%d%d%d%d", &start[0], &start[1], &end[0], &end[1]);
    
29.        
    
30.         map[start[0]][start[1]] = 1;
    
31.         search(start[0], start[1]);
    
32.        
    
33.         if(find_map(end[0], end[1], num))
    
34.                 printf("YES\n");
    
35.         else
    
36.                 printf("NO\n");
    
37. //        our_map(num);
    
38.         init(num);
    
39.        
    
40.         }
    
41.         return 0;
    
42. }
    
43. //---------------------------------
    
44. bool find_map(int x, int y, int n) {
    
45.         return map[x][y];
    
46. }
    
47. //---------------------------------
    
48. void in_maze(int n) {
    
49.         for(int i = 0; i < n; ++i) {
    
50.                 for(int j = 0; j < n; ++j) {
    
51.                         scanf(" %c", &maze[i][j]);
    
52.                 }
    
53.         }
    
54. }
    
55. //---------------------------------
    
56. int validate(int x, int y, int N){
    
57.     if(x >= 0 && x <= N - 1 && y >= 0 && y <= N - 1){
    
58.         return 1;
    
59.     }
    
60.     return 0;
    
61. }
    
62. //---------------------------------
    
63. void our_map(int num) {
    
64.         cout << endl << "map:" << endl;
    
65.         for(int i = 0; i < num; ++i) {
    
66.                 for(int j = 0; j < num; ++j) {
    
67.                         cout << map[i][j] << " ";
    
68.                 }
    
69.                 cout << endl;
    
70.         }
    
71. }
    
72. //---------------------------------
    
73. void init(int n) {
    
74.         for(int i = 0; i < n; ++i) {
    
75.                 for(int j = 0; j < n; ++j) {
    
76.                         maze[i][j] = 0;
    
77.                         map[i][j] = 0;
    
78.                         visit[i][j] = 0;
    
79.                 }
    
80.         }
    
81. }
    
82. //---------------------------------
    
83. void search(int x,int y){
    
84.         if(visit[x][y] == 1)
    
85.                 return;
    
86.         visit[x][y] = 1;
    
87.         for(int k = 0; k < 4; k++) {
    
88.                 int x1 = x + xstep[k];
    
89.                int y1 = y + ystep[k];
    
90.         if(validate(x1, y1, num) && maze[x][y] == '.') {
    
91.                 if(find_map(x1, y1, num)) {
    
92.                         map[x][y] = 1;
    
93.                         }
    
94.                 }
    
95.         }
    
96.     for (int i=0;i<4;i++){
    
97.         int x1=x+xstep[i];
    
98.         int y1=y+ystep[i];
    
99.         if(validate(x1,y1,num) && maze[x1][y1] == '.'){
    
100.             search(x1, y1);
     
101.         }
     
102.     }
     
103. }

复制代码

题目网站就一直10分只给我5分，怎么办呀，这是为什么

傻眼貓咪

1. #include <iostream>
   
2. #include <utility>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. int foo(vector <vector <char>> maze, pair <int, int> A, pair <int, int> B, int n) {
   
7.         auto &[r1, c1] = A;
   
8.         auto &[r2, c2] = B;
   
9.         if (r1 == r2 and c1 == c2) {
   
10.                 return 1;
    
11.         }
    
12.         else if (r1 < 0 or r2 < 0 or c1 < 0 or c2 < 0 or r1 >= n or r2 >= n or c1 >= n or c2 >= n) {
    
13.                 return 0;
    
14.         }
    
15.         else if (maze[r1][c1] != '.' or maze[r2][c2] != '.') return 0;
    
16.         vector <vector <char>> res = maze;
    
17.         res[r1][c1] = '#';
    
18.         return
    
19.                 foo(res, make_pair(r1 + 1, c1), B, n) +
    
20.                 foo(res, make_pair(r1 - 1, c1), B, n) +
    
21.                 foo(res, make_pair(r1, c1 + 1), B, n) +
    
22.                 foo(res, make_pair(r1, c1 - 1), B, n);
    
23. }
    
24. 
    
25. int main(void) {
    
26.         int n, k;
    
27.         vector <string> answer;
    
28.         cin >> k;
    
29.         for (int i = 0; i < k; ++i) {
    
30.                 cin >> n;
    
31.                 vector <vector <char>> maze (n, vector <char>(n, '#'));
    
32.                 for (int r = 0; r < n; ++r) {
    
33.                         for (int c = 0; c < n; ++c) {
    
34.                                 cin >> maze[r][c];
    
35.                         }
    
36.                 }
    
37.                 int x, y;
    
38.                 pair <int, int> A, B;
    
39.                 cin >> x >> y;
    
40.                 A = make_pair(x, y);
    
41.                 cin >> x >> y;
    
42.                 B = make_pair(x, y);
    
43.        
    
44.                 if (foo(maze, A, B, n)) {
    
45.                         answer.push_back("YES");
    
46.                 }
    
47.                 else {
    
48.                         answer.push_back("NO");
    
49.                 }
    
50.         }
    
51.        
    
52.         for (const string& str: answer) {
    
53.                 cout << str << endl;
    
54.         }
    
55.         return 0;
    
56. }

复制代码