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条回答 默认 最新

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

      • 创建了问题 3月21日

      悬赏问题

      • ¥15 关于#gstreamer webrtcbin#的问题,如何解决?
      • ¥15 怎么用c语言函数编写宿舍财务管理系统?
      • ¥15 css网页样式与布局
      • ¥15 三角剖分算法和Alpha shapes 算法求解
      • ¥15 关于#python#的问题:已有代码计算出了2018年—至今的5000+支A股的每日对数收益率,需要设计一种指标进行交易,分析年化收益和夏普比率
      • ¥15 c++模拟网上购书结账系统
      • ¥15 c语言查找数字并排序编程代码
      • ¥15 用stata编写,数据集是Excel形式
      • ¥15 希望得到帮助,希望得到帮助
      • ¥15 Win7电脑开机出现硬件设置已更改