一个大小为N*N，并且有若干个陷阱的迷宫，X星人现在站在迷宫左上角的起点(第1行第1列)，迷宫的终点是右下角(第N行第N列)。 X星人每次可以朝上、下、左、右四个方向行走，但不允许穿越墙壁。在迷宫中，“0”表示空地，“1”表示墙壁，“#”表示陷阱。X星人在迷宫中每行走一步需要1秒钟，但如果不幸掉入陷阱，则需要额外增加K秒的逃脱时间。如果终点位置恰好是陷阱，也需要计算时间。假设起点(左上角)既不是墙也不是陷阱，请问X星人从起点到终点最少需要多少时间?

区块链毕设网qklbishe.com为您提供问题的解答

深搜加回溯，代码如下：

#include <bits/stdc++.h>

using namespace std;

int n,k;

int dir[4][2]={0,1,0,-1,1,0,-1,0};

int ti;

int res=INT_MAX;

void dfs(vector<vector<char> >&tu,int x,int y ){

if(x==n-1&&y==n-1){

res=min(res,ti);

}

for(int i=0;i<4;i++){

int nx=x+dir[i][0];

int ny=y+dir[i][1];

if(nx<0||ny<0||nx>=n||ny>=n||tu[nx][ny]==‘1’||tu[nx][ny]==‘V’)continue;

char t=tu[x][y];

int tempTime=ti;

if(tu[x][y]==‘0’ )ti+=1;

if(tu[x][y]==‘#’)ti +=k;

tu[x][y]=‘V’;

dfs(tu,nx,ny);

ti=tempTime;

tu[x][y]=t;

}

int main() {

cin>>n>>k;

vector<vector<char> >tu(n,vector<char>(n));

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

cin>>tu[i][j];

}

dfs(tu,0,0);

cout<<res;

return 0;

}

// 64 位输出请用 printf("%lld")

07:05

以上就是关于问题一个大小为N*N，并且有若干个陷阱的迷宫，X星人现在站在迷宫左上角的起点(第1行第1列)，迷宫的终点是右下角(第N行第N列)。 X星人每次可以朝上、下、左、右四个方向行走，但不允许穿越墙壁。在迷宫中，“0”表示空地，“1”表示墙壁，“#”表示陷阱。X星人在迷宫中每行走一步需要1秒钟，但如果不幸掉入陷阱，则需要额外增加K秒的逃脱时间。如果终点位置恰好是陷阱，也需要计算时间。假设起点(左上角)既不是墙也不是陷阱，请问X星人从起点到终点最少需要多少时间?的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训