[求助] 01迷宫

柿子饼同学

题目在下边~
我的代码:

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool vis[1002][100002]; // 访问后的标记数组
   
5. int areas[1002][100002]; // 联通区域的图
   
6. bool mp[1002][100002]; // 存放迷宫
   
7. short dirx[] = {1, 0, -1, 0}; // x的4个方向
   
8. short diry[] = {0, 1, 0, -1}; // y的4个方向
   
9. int n, m, cnt = 1; // n, m -> 长, 宽
   
10. queue<int> x; // x, y 的队列 , 用宽搜的
    
11. queue<int> y;
    
12. map<int, int> cnts; // 每个区域对应的步数, <区域名, 步数>
    
13. 
    
14. void bfs(int px, int py){
    
15.     static int cnt = 1; // cnt -> 标记不同联通的区域
    
16.     int ans = 1; //步数初始化为 1
    
17.     x.push(px); y.push(py); vis[px][py] = 1;
    
18.     while(!x.empty()){
    
19.         for(int i = 0; i < 4; i++){
    
20.             int dx = x.front() + dirx[i];
    
21.             int dy = y.front() + diry[i];
    
22.             if(dx > 0 && dx <= n && dy > 0 && dy <= m && vis[dx][dy] == 0 && mp[dx][dy] != mp[x.front()][y.front()]){
    
23.                 x.push(dx); y.push(dy); vis[dx][dy] = 1; // 符合条件入队
    
24.                 areas[dx][dy] = cnt; // 给它标号
    
25.             }
    
26.         }
    
27.         ans++; // 每次搜索步数加 1
    
28.     }
    
29.     cnts[cnt] = ans; // 最后这个连通块的步数就求好了
    
30.     cnt++; // 下一个连通块的号加 1
    
31. }
    
32. 
    
33. void makeareas(){ // 把整个迷宫的不同联通区域弄出来
    
34.     for(int i = 1; i <= n; i++){
    
35.         for(int j = 1; j <= m; j++){
    
36.             if(!vis[i][j]) bfs(i, j); //没访问过就访问
    
37.         }
    
38.     }
    
39. }
    
40. 
    
41. int main(){
    
42.     ios::sync_with_stdio(0);
    
43. 
    
44.     memset(vis, 0, sizeof(vis));
    
45.    
    
46.     cin >> n >> m;
    
47.     for(int i = 1; i <= n; i++){
    
48.         for(int j = 1; j <= m; j++){
    
49.             char temp;
    
50.             cin >> temp;
    
51.             mp[i][j] = (bool)(temp - '0');
    
52.         }
    
53.     } // 输入 , 因为只有 0 和 1 , 所以省空间就用了 bool 存
    
54. 
    
55.     makeareas();
    
56. 
    
57.     for(int i = 0; i < m; i++){
    
58.         int p, q;
    
59.         cin >> p >> q;
    
60.         cout << cnts[areas[p][q]] << endl;
    
61.     } // 输出 , 把它所在的连通块的标号求出 , 然后就可以知道步数 , 输出
    
62. 
    
63.     return 0;
    
64. }

复制代码

题目 : https://www.luogu.com.cn/problem/P1141
代码检查不出来, 到输入坐标的时候输不进去, 救助
另外我这个代码还有哪里有不好的地方请指出, 谢谢~

柿子饼同学

救救我吧

傻眼貓咪

我的思路：
用递归吧，走过的路线标记起来，当上下左右没有路线时，则返回最终步数，并且找出上下左右最长的路线便是答案。

递：用来算步数
归：用来比较最大值

jhq999

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int makeareas(int (*mp)[2],int n,int x,int y,int len,int *max)
   
4. {
   
5.     int i,j;
   
6.     if(mp[x*n+y][0]^mp[x*n+y+1][0]&&(0==mp[x*n+y+1][1])&&(y+1<n))
   
7.     {
   
8.         mp[x*n+y+1][1]=1;
   
9.         makeareas(mp,n,x,y+1,len+1,max);
   
10.         mp[x*n+y+1][1]=0;
    
11.     }
    
12.     if(mp[x*n+y][0]^mp[x*n+y-1][0]&&(0==mp[x*n+y-1][1])&&(y-1>=0))
    
13.     {
    
14.         mp[x*n+y-1][1]=1;
    
15.         makeareas(mp,n,x,y-1,len+1,max);
    
16.         mp[x*n+y-1][1]=0;
    
17.     }
    
18.     if(mp[x*n+y][0]^mp[(x+1)*n+y][0]&&(0==mp[(x+1)*n+y][1])&&(x+1<n))
    
19.     {
    
20.         mp[(x+1)*n+y][1]=1;
    
21.         makeareas(mp,n,x+1,y,len+1,max);
    
22.         mp[(x+1)*n+y][1]=0;
    
23.     }
    
24.      if(mp[x*n+y][0]^mp[(x-1)*n+y][0]&&(0==mp[(x-1)*n+y][1])&&(x-1>=0))
    
25.     {
    
26.         mp[(x-1)*n+y][1]=1;
    
27.         makeareas(mp,n,x-1,y,len+1,max);
    
28.         mp[(x-1)*n+y][1]=0;
    
29.     }
    
30.     if(*max<len)*max=len;
    
31.     return 0;
    
32. }
    
33. int main(){
    
34.     ios::sync_with_stdio(0);
    
35.     int n,m,i,j;
    
36.     cin >> n >> m;
    
37.     int (*mp)[2]=(int(*)[2])malloc(sizeof(int)*n*n*2);
    
38.     for(i=0;i<n;i++)
    
39.     {
    
40.         for(j=0;j<n;j++)
    
41.         {
    
42.             cin>>mp[i*n+j][0];
    
43.             mp[i*n+j][1]=0;
    
44.         }
    
45.     }
    
46.     int max=0;
    
47.     mp[0][1]=1;
    
48.     makeareas(mp,n,0,0,1,&max);
    
49.     // 输入 , 因为只有 0 和 1 , 所以省空间就用了 bool 存
    
50. 
    
51.     //makeareas();
    
52.     printf("%d",max);
    
53.     free(mp);
    
54.     return 0;
    
55. }

复制代码

柿子饼同学

傻眼貓咪 发表于 2022-6-11 18:58
我的思路：
用递归吧，走过的路线标记起来，当上下左右没有路线时，则返回最终步数，并且找出上下左右最长 ...

可是它要搜十万次...
这不行吧

傻眼貓咪

柿子饼同学 发表于 2022-6-11 22:29
可是它要搜十万次...
这不行吧

好象也是