【每日一题】【最短路】【BFS】小红走矩阵 “葡萄城杯”牛客周赛 Round 53 F题 C++

“葡萄城杯”牛客周赛 Round 53 F题

小红走矩阵

题目背景

“葡萄城杯”牛客周赛 Round 53

题目描述

$n\times m$的矩阵由障碍和空地组成，初始时小红位于起点$(1,1)$，她想要前往终点$(n,m)$。小红每一步可以往上下左右四个方向的空地移动一格。

小红在起点处可以进行最多一次操作：选择矩阵中的一处障碍替换为空地，但代价是小红必须选择失去向上下左右四个方向中一个移动的能力。

求小红从起点到达终点的最小步数，如果无法到达则输出$-1$

输入格式

第一行输入两个整数 $n,m(1\le n,m\le 1000)$代表矩阵的大小。

此后 $n$ 行，每行输入 $m$个字符 a 1 a 2 . . . a n ( a i ∈ { ′ X ′ , ′ . ′ } ) a_1a_2...a_n(a_i\in{\{'X','.'\}}) a1​a2​...an​(ai​∈{′X′,′.′})描述矩阵中这一行的情况，其中${}^{\prime }{X}^{\prime }$（Ascii：88）代表障碍，${}^{\prime }{.}^{\prime }$（Ascii：46）代表空地。保证起点和终点都是空地

输出格式

在一行上输出一个整数，表示小红从起点到达终点的最小步数；如果无论怎么操作都无法到达，则直接输出$-1$

样例 #1

样例输入 #1

4 4
..X.
XXX.
.X..
.X..

样例输出 #1

6

说明

小红失去向上走的能力，消除$(1,3)$处障碍，从起点到终点的最小步数为$6$。

样例 #2

样例输入 #2

4 4
.XX.
XXX.
.X..
.X..

样例输出 #2

-1

说明

小红最多只能删除一个障碍，无法到达终点。

做题要点

1. 起点处可以进行最多一次操作
2. 选择失去向上下左右四个方向中一个移动的能力
3. 最短路
4. $n,m(1\le n,m\le 1000)$

做题难点

没处理好删除一个障碍和不删除障碍的最短路关系。
如果混在一起都记为到当前格子最短路。
那么就可能出现情况有删除障碍提前到达更新了最短路，导致不删除障碍后达的无法更新最短路并加入后续bfs中，但后续又有障碍，因为只能删除一个障碍，就会导致本来有解变无解。

做题思路

这道题为典型的最短路变种问题，通常使用方法为广度优先搜索(BFS)。

首先如果不考虑失去一个方向移动能力和删除操作。

普通的跑一次BFS，可记为第一种答案。

BFS基本套路为:

1. 初始化队列和标记数组(花费数组)，将起点加入队列
2. 取队列元素并出队，根据当前元素进行下一步行走(判断+更新+入队)
3. 重复第二步直到队列为空

还有就是禁掉(ban)一个移动能力然后再跑一次BFS，这次加入可以穿越障碍一次的判断即可。

因为有四个方向，所以跑四次BFS。

重点在于如何处理好删除一个障碍和不删除障碍的最短路关系。
如果设的是花费数组那么二维的数组$cn{t}_{i,j}$是不够的，因为二维的记录当前坐标的最短路，可能会产生删除障碍到$(i,j)$的最短路为$k$，而不删除障碍到$(i,j)$的最短路为$k+a$,$a\ge 1$，然后从$(i,j)$到终点还有障碍(必须穿过)，就会导致在前面就用掉了这次删除障碍的机会。后面不删除的因为最短路并不是最短的无法继续入队执行BFS导致最后答案为无解。

如果额外想办法以消耗时间的方法去解决，很容易导致TLE(超时)

这里就需要用额外空间的方法去解决，设三维数组$cn{t}_{i,j,k}$其中第三维大小为2，即布尔下标，其中$k=true/1$时候表示为从起点到$(i,j)$的没消耗删除障碍次数的最短路，
反之$k=false/0$时候表示为从起点到$(i,j)$的消耗删除障碍次数的最短路。

最后本次到终点的最短路取两者的最小值即可。

总结思路

1. 普通BFS一次
2. ban掉四个方向各一次并跑BFS
3. 取所以答案的最短路最小值

核心代码对应思路

ban掉四个方向各一次并跑BFS

bfs();
for(int i=0;i<4;i++){memset(cnt,0x3f,sizeof(cnt));//重置花费数组memset(cut,true,sizeof(cut));//重置禁止数组cut[i] = false;//ban掉该方向bfs2();
}

处理好删除一个障碍和不删除障碍的最短路关系

                if(a[nx][ny] == '.' && cnt[nx][ny][have] > cnt[x][y][have] + 1){cnt[nx][ny][have] = cnt[x][y][have] + 1;q.push(make_tuple(nx,ny,have));}else if(a[nx][ny] == 'X' && have && cnt[nx][ny][false] > cnt[x][y][have] + 1){cnt[nx][ny][false] = cnt[x][y][have] + 1;//!!!q.push(make_tuple(nx,ny,false));}

时间复杂度分析

相当于跑五次BFS为$O(5n\times m)$

伪代码

代码

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,ans = INF;
char a[N][N];
int cnt[N][N][2];
int bt[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
bool cut[4];
void init(){cin >> n >> m;//for(int i=1;i<=n;i++)cin >> a[i];//for(int i=1;i<=n;i++)a[i] = " " + a[i];memset(cnt,0x3f,sizeof(cnt));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin >> a[i][j];
}
inline bool check(int x,int y){return x>=1 && x<=n && y>=1 && y<=m;
}
void bfs(){int x,y,nx,ny;queue<pair<int,int> > q;cnt[1][1][0] = 0;q.push(make_pair(1,1));while(!q.empty()){tie(x,y) = q.front();q.pop();for(int i=0;i<4;i++){nx = x + bt[i][0];ny = y + bt[i][1];if(check(nx,ny) && a[nx][ny] == '.' && cnt[nx][ny][0] > cnt[x][y][0] + 1){cnt[nx][ny][0] = cnt[x][y][0] + 1;q.push(make_pair(nx,ny));}}}ans = min(ans,cnt[n][m][0]);
}
void bfs2(){int x,y,nx,ny;bool have;queue<tuple<int,int,bool> > q;cnt[1][1][1] = 0;q.push(make_tuple(1,1,true));while(!q.empty()){tie(x,y,have) = q.front();q.pop();for(int i=0;i<4;i++){if(!cut[i])continue;nx = x + bt[i][0];ny = y + bt[i][1];if(check(nx,ny)){if(a[nx][ny] == '.' && cnt[nx][ny][have] > cnt[x][y][have] + 1){cnt[nx][ny][have] = cnt[x][y][have] + 1;q.push(make_tuple(nx,ny,have));}else if(a[nx][ny] == 'X' && have && cnt[nx][ny][false] > cnt[x][y][have] + 1){cnt[nx][ny][false] = cnt[x][y][have] + 1;q.push(make_tuple(nx,ny,false));}}}}ans = min({ans,cnt[n][m][false],cnt[n][m][true]});
}
int main(){init();bfs();for(int i=0;i<4;i++){memset(cnt,0x3f,sizeof(cnt));memset(cut,true,sizeof(cut));cut[i] = false;bfs2();}if(ans == INF)cout << -1;else cout << ans;return 0;
}