m0_62148181 2023-03-21 00:25 采纳率: 0%
浏览 24

蓝桥杯迷宫题 遇到了错误,不知道是哪里写错了,用的是DFS思路,图里面那个简单的用例

蓝桥杯迷宫题

##遇到了错误,不知道是哪里写错了,用的是DFS思路,图里面那个简单的用例

img


#include<bits/stdc++.h>
using namespace std;
int tox[] = {1,0,0,-1};
int toy[] = {0,-1,1,0};
char dir[] = {'D','L','R','U'};

const int row = 4;
const int col = 6;
string maze[row]={
   "010000",
   "000100",
   "001001",
   "110000"
};
int mins[row+5][col+5];
int best = 1e8+5;
char a[row*col];
string ans;
string temp;

void dfs(int x , int y , int step){
   if(step > best) return;
   if(x == row - 1 && y == col - 1) {
       for(int i=1;i<step;i++)
           temp+=a[i];
       if(step < best)
           best = step;
           ans = temp;
       return;
   }
   else if(step==best && temp<ans)    ans=temp;
   for(int i = 0 ; i < 4 ; i++){
       int nextx = x + tox[i];
       int nexty = y + toy[i];
       if(nextx >= 0 && nextx <= row - 1 && nexty >= 0 && nexty <= col - 1 && maze[nextx][nexty]=='0' && step + 1 <= mins[nextx][nexty]){
           mins[nextx][nexty] = step +1;
           maze[nextx][nexty] = '1';
           a[step] = dir[i];
           dfs(nextx , nexty , step+1);
           maze[nextx][nexty] = '0';
       }
   }
}

int main(){
   memset(mins,1,sizeof(mins));
   maze[0][0] = '1';
   dfs(0, 0 ,0);
   cout<< best<<endl;
   cout<< ans;
   return 0;
}

img

##正确答案应该是

img

  • 写回答

2条回答 默认 最新

  • CSDN-Ada助手 CSDN-AI 官方账号 2023-03-21 09:22
    关注
    不知道你这个问题是否已经解决, 如果还没有解决的话:

    如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^
    评论
  • 赵4老师 2023-03-21 09:29
    关注

    仅供参考:

    /**
     * @Title  老鼠走迷宫的拓展探究
     * @Author 孙琨
     * @Date   2013-11-16
     * @At     XUST
     * @All Copyright by 孙琨
     *
     */
    
    #include <iostream>
    using namespace std;
    
    int maze[9][9] = { // 初始化迷宫,英文maze为“迷宫”
        {2,2,2,2,2,2,2,2,2},
        {2,0,0,0,0,0,0,0,2},
        {2,0,2,2,0,2,2,0,2},
        {2,0,2,0,0,2,0,0,2},
        {2,0,2,0,2,0,2,0,2},
        {2,0,0,0,0,0,2,0,2},
        {2,2,0,2,2,0,2,2,2},
        {2,0,0,0,0,0,0,0,2},
        {2,2,2,2,2,2,2,2,2}
    };
    
    int startI = 1,startJ = 1; // 入口行列坐标
    int endI = 7,endJ = 7;     // 出口行列坐标
    
    void visit(int i,int j)  // 自动搜寻路径
    {
        int m,n;
    
        maze[i][j] = 1;
    
        if((i == endI) && (j == endJ))
        {
            cout << endl << "显示路径:" << endl;
            for(m=0; m<9; m++)
            {
                for(n=0; n<9; n++)
                {
                    if(maze[m][n] == 2)
                        cout << "■";
                    else if(maze[m][n] == 1)
                        cout << "♀";
                    else
                        cout << "  ";
                }
                cout << endl;
            }
        }
    
        if(maze[i][j+1] == 0)
            visit(i,j+1);
        if(maze[i+1][j] == 0)
            visit(i+1,j);
        if(maze[i][j-1] == 0)
            visit(i,j-1);
        if(maze[i-1][j] == 0)
            visit(i-1,j);
    
        maze[i][j] = 0;
    
    }
    
    int main(void)
    {
        int i,j;
    
        cout << "显示迷宫: " << endl;
        for(i=0; i<9; i++)
        {
            for(j=0; j<9; j++)
            {
                if(maze[i][j] == 2)
                    cout << "■" ;
                else
                    cout << "  " ;
            }
            cout << endl;
        }
    
        visit(startI,startJ);
    
        return 0;
    }
    
    
    
    
    评论

报告相同问题?

问题事件

  • 创建了问题 3月21日

悬赏问题

  • ¥15 求苹果推信imessage批量推信技术
  • ¥15 ubuntu 22.04 系统盘空间不足。隐藏的docker空间占用?(相关搜索:移动硬盘|管理系统)
  • ¥15 利用加权最小二乘法求亚马逊各类商品的价格指标?怎么求?
  • ¥15 c++ word自动化,为什么可用接口是空的?
  • ¥15 Matlab计算100000*100000的矩阵运算问题:
  • ¥50 VB6.0如何识别粘连的不规则的数字图片验证码
  • ¥16 需要完整的这份订单所有的代码,可以加钱
  • ¥15 Stata数据分析请教
  • ¥15 请教如何为VS2022搭建 Debug|win32的openCV环境?
  • ¥15 关于#c++#的问题:c++如何使用websocketpp实现websocket接口调用,求示例代码和相关资料