逃离迷宫

题目描述

小智被大坏蛋抓进一间有A x A个格子组成的矩阵迷宫。用 * 表示的是小智可以经过的格子；用 # 表示的是小智不可以经过的格子。小智的起始位置在左上角，他需要到达右下角的格子才能逃离迷宫。小智每一步可以移动到上下左右四个方向相邻的格子上，前提是目标格式必须是没有障碍的。

现在小智可以用魔法移除格子上的障碍，也就是 # 变成 *，使其可以经过。请你计算在最多能移除B处障碍的情况下，小智最少移动多少步可以逃离迷宫。

输入 第一行包含2个整数A和B。 以下A行包含一个A x A的矩阵。 矩阵保证左上角和右下角是 *。 输出 一个整数表示答案。如果小智不能逃离迷宫，输出-1。

样例输入
5 2
*#*#*
#*#*#
*###*
#***#
*#***
样例输出 8

解题思路

很明显是可以用dfs解决的走迷宫问题。但是这个要求找到最少移动多少步，所以我们要记录每次找到的路径的步数，找到其中最小的。

我们注意到，这个题可以移除格子上的障碍，也就是 # 变成 *，但是最多消除 b 处。所以我们可以用一个变量记录到目前为止共消除了多少个，只要这个数是小于等于b的，那么我们就可以继续走。

递归终止条件就是走到了右下角，并且此时消除的障碍的个数小于等于b。递归过程，就是我们尝试向四个方向走一步，如果走这一步到达的地方是在迷宫范围内。并且没有走过，并且此时消除障碍的个数小于等于b，那么我们就可以走这一步，并继续往下走。注意在走的时候，我们完全不需要判断这个点是障碍，还是通路，我们只需要判断当前消除障碍的个数就好了。

代码如下

#include<bits/stdc++.h> using namespace std; char s[1000][1000]; bool vis[1000][1000];//标记是否走过 int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};//表示四个方向 int a,b; int ans = 1e9;//找到最小的那个步数 int v = 0;//记录找到的路径的个数，如果没找到就要输出-1 //需要维护的四个值，当前的坐标x,y,以及当前走的步数，还有到目前为止消除障碍的个数。 void dfs(int x,int y,int cnt,int num){ if(x == a-1 && y == a-1 && num<=b){   ans = min(ans,cnt);   v++; return; } //printf("1111n"); for(int i = 0; i<4; i++){ int p = x+dir[i][0]; int q = y+dir[i][1]; if(p >= 0 && p < a && q >= 0 && q < a && vis[p][q] == false && num<=b){    vis[p][q] = true;//标记这个点走过    cnt++;//走的步数加1 if(s[p][q] == '#') num++;//如果这个地方是障碍，那么我们消除障碍的个数就要加1 dfs(p,q,cnt,num);    vis[p][q] = false;    cnt--; if(s[p][q] == '#') num--; } } return; } int main(){ scanf("%d%d",&a,&b); for(int i = 0; i< a; i++){ scanf("%s",s[i]); } memset(vis,false,sizeof(vis));  vis[0][0] = true; dfs(0,0,0,0); if(v == 0) printf("-1"); else printf("%d",ans); return 0; }