柿子饼同学 发表于 2022-6-11 16:09:39

[求助] 01迷宫

本帖最后由 柿子饼同学 于 2022-6-11 18:19 编辑

题目在下边~
我的代码:
#include <bits/stdc++.h>
using namespace std;

bool vis; // 访问后的标记数组
int areas; // 联通区域的图
bool mp; // 存放迷宫
short dirx[] = {1, 0, -1, 0}; // x的4个方向
short diry[] = {0, 1, 0, -1}; // y的4个方向
int n, m, cnt = 1; // n, m -> 长, 宽
queue<int> x; // x, y 的队列 , 用宽搜的
queue<int> y;
map<int, int> cnts; // 每个区域对应的步数, <区域名, 步数>

void bfs(int px, int py){
    static int cnt = 1; // cnt -> 标记不同联通的区域
    int ans = 1; //步数初始化为 1
    x.push(px); y.push(py); vis = 1;
    while(!x.empty()){
      for(int i = 0; i < 4; i++){
            int dx = x.front() + dirx;
            int dy = y.front() + diry;
            if(dx > 0 && dx <= n && dy > 0 && dy <= m && vis == 0 && mp != mp){
                x.push(dx); y.push(dy); vis = 1; // 符合条件入队
                areas = cnt; // 给它标号
            }
      }
      ans++; // 每次搜索步数加 1
    }
    cnts = ans; // 最后这个连通块的步数就求好了
    cnt++; // 下一个连通块的号加 1
}

void makeareas(){ // 把整个迷宫的不同联通区域弄出来
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
            if(!vis) bfs(i, j); //没访问过就访问
      }
    }
}

int main(){
    ios::sync_with_stdio(0);

    memset(vis, 0, sizeof(vis));
   
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
            char temp;
            cin >> temp;
            mp = (bool)(temp - '0');
      }
    } // 输入 , 因为只有 0 和 1 , 所以省空间就用了 bool 存

    makeareas();

    for(int i = 0; i < m; i++){
      int p, q;
      cin >> p >> q;
      cout << cnts] << endl;
    } // 输出 , 把它所在的连通块的标号求出 , 然后就可以知道步数 , 输出

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

柿子饼同学 发表于 2022-6-11 18:17:55

{:10_266:}{:10_266:}{:10_266:}
救救我吧

傻眼貓咪 发表于 2022-6-11 18:58:43

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

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

jhq999 发表于 2022-6-11 19:58:05

本帖最后由 jhq999 于 2022-6-11 19:59 编辑

#include <bits/stdc++.h>
using namespace std;
int makeareas(int (*mp),int n,int x,int y,int len,int *max)
{
    int i,j;
    if(mp^mp&&(0==mp)&&(y+1<n))
    {
      mp=1;
      makeareas(mp,n,x,y+1,len+1,max);
      mp=0;
    }
    if(mp^mp&&(0==mp)&&(y-1>=0))
    {
      mp=1;
      makeareas(mp,n,x,y-1,len+1,max);
      mp=0;
    }
    if(mp^mp[(x+1)*n+y]&&(0==mp[(x+1)*n+y])&&(x+1<n))
    {
      mp[(x+1)*n+y]=1;
      makeareas(mp,n,x+1,y,len+1,max);
      mp[(x+1)*n+y]=0;
    }
   if(mp^mp[(x-1)*n+y]&&(0==mp[(x-1)*n+y])&&(x-1>=0))
    {
      mp[(x-1)*n+y]=1;
      makeareas(mp,n,x-1,y,len+1,max);
      mp[(x-1)*n+y]=0;
    }
    if(*max<len)*max=len;
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    int n,m,i,j;
    cin >> n >> m;
    int (*mp)=(int(*))malloc(sizeof(int)*n*n*2);
    for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
      {
            cin>>mp;
            mp=0;
      }
    }
    int max=0;
    mp=1;
    makeareas(mp,n,0,0,1,&max);
    // 输入 , 因为只有 0 和 1 , 所以省空间就用了 bool 存

    //makeareas();
    printf("%d",max);
    free(mp);
    return 0;
}

柿子饼同学 发表于 2022-6-11 22:29:05

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

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

傻眼貓咪 发表于 2022-6-11 22:49:24

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

好象也是{:5_99:}
页: [1]
查看完整版本: [求助] 01迷宫