最短路径 矩阵 dfs 有障碍

游戏地图路径

https://www.nowcoder.com/practice/a4b7f297ad0e46a0a1fbac4d2da83a63?tab=note

alt

using namespace std;
#include<vector>
void dfs(const vector<vector<char>>& vec,int beginX,int beginY,int endX,int endY,const int n,vector<vector<int>>& memory,int count){
    if(beginX<0||beginX>=n||beginY<0||beginY>=n) return; // 越界
    if(vec[beginX][beginY]=='#'||vec[beginX][beginY]=='@') return;  // 障碍
    if(memory[beginX][beginY]!=0 && memory[beginX][beginY]<=count) return ; // 已经访问过或者记忆数组记录的距离更小
    memory[beginX][beginY]=count; // 记录当前距离
    if(beginX==endX && beginY==endY) return; // 到达终点
    dfs(vec, beginX-1, beginY, endX, endY,  n, memory,count+1);
    dfs(vec, beginX+1, beginY, endX, endY,  n, memory,count+1);
    dfs(vec, beginX, beginY+1, endX, endY,  n, memory,count+1);
    dfs(vec, beginX, beginY-1, endX, endY,  n, memory,count+1);  
}
int main(){
    int n=0;cin>>n;
    vector<vector<char>>vec(n,vector<char>());
    int beginX=0;int beginY=0;int endX=0;int endY=0;
    cin>>beginY>>beginX>>endY>>endX;
    for(int i=0;i<n;i++){
        string a;cin>>a;
        for(auto it:a){
            vec[i].push_back(it);
        }
    }
    vector<vector<int>> memory(n,vector<int>(n,0));
    dfs(vec,beginX,beginY,endX,endY,n,memory,1);
    if(memory[endX][endY]==0) cout<<-1<<endl;
    else cout<<memory[endX][endY]-1<<endl;
    return 0;
}
全部评论

相关推荐

1.自我介绍2.介绍一下mcp,&nbsp;skills3.了解react哪些状态管理库4.对话是sse还是什么?是用fetch还是EventSource?5.ts中的any&nbsp;和&nbsp;unknown讲一讲6.是直接用组件库的组件还是自己封装了一些别的7.代码输出题1function&nbsp;main()&nbsp;{{var&nbsp;a&nbsp;=&nbsp;1let&nbsp;b&nbsp;=&nbsp;2}console.log(a);console.log(b);}main()console.log(a);8.什么是块级作用域&nbsp;全局作用域&nbsp;函数作用域9.代码输出题2for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(i);},&nbsp;100);}10.代码输出题3for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&amp;lt;&nbsp;5;&nbsp;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}11.代码输出题4for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{var&nbsp;temp&nbsp;=&nbsp;isetTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}12.代码输出题5for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{var&nbsp;temp&nbsp;=&nbsp;iconsole.log(temp);},&nbsp;100);}printText(i)}13.点击控制台输出题export&nbsp;default&nbsp;function&nbsp;App()&nbsp;{const&nbsp;[count,&nbsp;setCount]&nbsp;=&nbsp;useState(0)console.log('render',count)return&nbsp;(&lt;div&gt;&lt;h1&gt;{count}&lt;/h1&gt;{setCount(count&nbsp;+&nbsp;1)setTimeout(()&nbsp;=&amp;gt;&nbsp;console.log('setTimeout',&nbsp;count),&nbsp;1000)}}&amp;gt;+1&lt;/div&gt;)}//这个组件点击按钮后,控制台的输出顺序和值如下://&nbsp;1.&nbsp;render&nbsp;1&nbsp;(组件重新渲染,&nbsp;count&nbsp;更新为&nbsp;1)//&nbsp;2.&nbsp;setTimeout&nbsp;0&nbsp;(1秒后输出,注意这里是&nbsp;0&nbsp;而不是&nbsp;1)14.算法:给有序数组arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5],返回平方后的排序//&nbsp;有序数组平方后排序const&nbsp;arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5]function&nbsp;solution(arr)&nbsp;{const&nbsp;len&nbsp;=&nbsp;arr.lengthconst&nbsp;result&nbsp;=&nbsp;new&nbsp;Array(len)let&nbsp;left&nbsp;=&nbsp;0let&nbsp;right&nbsp;=&nbsp;len&nbsp;-&nbsp;1let&nbsp;index&nbsp;=&nbsp;len&nbsp;-&nbsp;1while&nbsp;(left&nbsp;&amp;lt;=&nbsp;right)&nbsp;{if&nbsp;(arr[left]&nbsp;*&nbsp;arr[left]&nbsp;&amp;gt;&nbsp;arr[right]&nbsp;*&nbsp;arr[right])&nbsp;{result[index]&nbsp;=&nbsp;arr[left]&nbsp;*&nbsp;arr[left]left++}&nbsp;else&nbsp;{result[index]&nbsp;=&nbsp;arr[right]&nbsp;*&nbsp;arr[right]right--}index--}return&nbsp;result}console.log(solution(arr));15.反问
查看14道真题和解析
点赞 评论 收藏
分享
01-30 16:13
浙江大学 Java
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务