蓝桥杯迷宫题
##遇到了错误,不知道是哪里写错了,用的是DFS思路,图里面那个简单的用例
#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;
}
##正确答案应该是