[求助] 01迷宫

柿子饼同学

题目在下边~
我的代码:

#include <bits/stdc++.h>
using namespace std;

bool vis[1002][100002]; // 访问后的标记数组
int areas[1002][100002]; // 联通区域的图
bool mp[1002][100002]; // 存放迷宫
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[px][py] = 1; 
    while(!x.empty()){
        for(int i = 0; i < 4; i++){
            int dx = x.front() + dirx[i];
            int dy = y.front() + diry[i];
            if(dx > 0 && dx <= n && dy > 0 && dy <= m && vis[dx][dy] == 0 && mp[dx][dy] != mp[x.front()][y.front()]){
                x.push(dx); y.push(dy); vis[dx][dy] = 1; // 符合条件入队
                areas[dx][dy] = cnt; // 给它标号
            }
        }
        ans++; // 每次搜索步数加 1
    }
    cnts[cnt] = ans; // 最后这个连通块的步数就求好了
    cnt++; // 下一个连通块的号加 1
}

void makeareas(){ // 把整个迷宫的不同联通区域弄出来
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!vis[i][j]) 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[i][j] = (bool)(temp - '0');
        }
    } // 输入 , 因为只有 0 和 1 , 所以省空间就用了 bool 存

    makeareas();

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

    return 0;
}

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

柿子饼同学

救救我吧

傻眼貓咪

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

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

jhq999

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

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

柿子饼同学

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

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

傻眼貓咪

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

好象也是