逃离迷宫6

题目名称：逃离迷宫6

题目链接：逃离迷宫6

描述

小Hi被坏女巫抓进里一间有N x N个格子组成的矩阵迷宫。

有些格子是小Hi可以经过的，我们用’.‘表示；有些格子上有障碍物小Hi不能经过，我们用’#'表示。小Hi的起始位置在左上角，他需要到达右下角的格子才能逃离迷宫。小Hi每一步可以移动到上下左右四个方向相邻的格子上，前提是目标格式必须是没有障碍的。

现在小Hi可以用魔法移除格子上的障碍，也就是’#‘变成’.’，使其可以经过。

请你计算在最多能移除K处障碍的情况下，小Hi最少移动多少步可以逃离迷宫。

输入

第一行包含2个整数N和K。

以下N行包含一个N x N的矩阵。

矩阵保证左上角和右下角是’.’。

对于70%的数据，1 <= N <= 100

对于100%的数据，1 <= N <= 1000 1 <= K <= 10

输出

一个整数表示答案。如果小Hi不能逃离迷宫，输出-1。

样例输入

5 2
.#.#.
#.#.#
.###.
#…#
.#…

样例输出

8

解题思路

创建三维数组表示X，Y，坐标和在该坐标下已经穿过了几次障碍，使用宽度优先搜索算法即可解决问题

完整代码

#include
#include
#include
#include
#include
using namespace std;
#define N 1010
char s[N];
bool obstacle[N][N];struct Node{int x,y,cnt,dis;Node(){}Node(int x,int y,int cnt,int dis):x(x),y(y),cnt(cnt),dis(dis){}friend bool operator <(const Node &a,const Node &b){return a.dis>b.dis;}
}front;
priority_queueque;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dis[N][N][15];
int n,k;void bfs(){memset(dis,0x3f,sizeof(dis));dis[1][1][0]=0;que.push(Node(1,1,0,0));int u,v,t; while(!que.empty()){front=que.top();que.pop();for(int i=0;i<4;i++){u=front.x+dx[i];v=front.y+dy[i];t=front.cnt+obstacle[u][v];if (t<=k&&u&&v&&u<=n&&v<=n&&dis[u][v][t]>dis[front.x][front.y][front.cnt]+ 1){dis[u][v][t] = dis[front.x][front.y][front.cnt] + 1;que.push(Node(u, v, t, dis[u][v][t]));}}}int ans=n*n;for (int i=0;i<=k;i++)ans = min(ans,dis[n][n][i]);printf("%d\n", ans);
}int main()
{scanf("%d%d",&n,&k);
//	cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！