乐清网站制作电话,网站建设设备预算,鞍山吧 百度贴吧,wordpress怎么上传高清图片大小“葡萄城杯”牛客周赛 Round 53 F题
小红走矩阵
题目背景
“葡萄城杯”牛客周赛 Round 53
题目描述 n m n\times m nm的矩阵由障碍和空地组成#xff0c;初始时小红位于起点 ( 1 , 1 ) (1,1) (1,1)#xff0c;她想要前往终点 ( n , m ) (n,m) (n,m)。小红每一步可以往上…“葡萄城杯”牛客周赛 Round 53 F题
小红走矩阵
题目背景
“葡萄城杯”牛客周赛 Round 53
题目描述 n × m n\times m n×m的矩阵由障碍和空地组成初始时小红位于起点 ( 1 , 1 ) (1,1) (1,1)她想要前往终点 ( n , m ) (n,m) (n,m)。小红每一步可以往上下左右四个方向的空地移动一格。
小红在起点处可以进行最多一次操作选择矩阵中的一处障碍替换为空地但代价是小红必须选择失去向上下左右四个方向中一个移动的能力。
求小红从起点到达终点的最小步数如果无法到达则输出 − 1 -1 −1
输入格式
第一行输入两个整数 n , m ( 1 ≤ n , m ≤ 1000 ) n, m(1\le n ,m \le 1000) n,m(1≤n,m≤1000)代表矩阵的大小。
此后 n n n 行每行输入 m m m个字符 a 1 a 2 . . . a n ( a i ∈ { ′ X ′ , ′ . ′ } ) a_1a_2...a_n(a_i\in{\{X,.\}}) a1a2...an(ai∈{′X′,′.′})描述矩阵中这一行的情况其中 ′ X ′ X ′X′Ascii88代表障碍 ′ . ′ . ′.′Ascii46代表空地。保证起点和终点都是空地
输出格式
在一行上输出一个整数表示小红从起点到达终点的最小步数如果无论怎么操作都无法到达则直接输出 − 1 -1 −1
样例 #1
样例输入 #1
4 4
..X.
XXX.
.X..
.X..样例输出 #1
6说明
小红失去向上走的能力消除 ( 1 , 3 ) (1,3) (1,3)处障碍从起点到终点的最小步数为 6 6 6。
样例 #2
样例输入 #2
4 4
.XX.
XXX.
.X..
.X..样例输出 #2
-1说明
小红最多只能删除一个障碍无法到达终点。
做题要点
起点处可以进行最多一次操作选择失去向上下左右四个方向中一个移动的能力最短路 n , m ( 1 ≤ n , m ≤ 1000 ) n, m(1\le n ,m \le 1000) n,m(1≤n,m≤1000)
做题难点
没处理好删除一个障碍和不删除障碍的最短路关系。 如果混在一起都记为到当前格子最短路。 那么就可能出现情况有删除障碍提前到达更新了最短路导致不删除障碍后达的无法更新最短路并加入后续bfs中但后续又有障碍因为只能删除一个障碍就会导致本来有解变无解。
做题思路
这道题为典型的最短路变种问题通常使用方法为广度优先搜索(BFS)。
首先如果不考虑失去一个方向移动能力和删除操作。
普通的跑一次BFS可记为第一种答案。
BFS基本套路为:
初始化队列和标记数组(花费数组)将起点加入队列取队列元素并出队根据当前元素进行下一步行走(判断更新入队)重复第二步直到队列为空
还有就是禁掉(ban)一个移动能力然后再跑一次BFS这次加入可以穿越障碍一次的判断即可。
因为有四个方向所以跑四次BFS。
重点在于如何处理好删除一个障碍和不删除障碍的最短路关系。 如果设的是花费数组那么二维的数组 c n t i , j cnt_{i,j} cnti,j是不够的因为二维的记录当前坐标的最短路可能会产生删除障碍到 ( i , j ) (i,j) (i,j)的最短路为 k k k而不删除障碍到 ( i , j ) (i,j) (i,j)的最短路为 k a ka ka, a ≥ 1 a \ge 1 a≥1然后从 ( i , j ) (i,j) (i,j)到终点还有障碍(必须穿过)就会导致在前面就用掉了这次删除障碍的机会。后面不删除的因为最短路并不是最短的无法继续入队执行BFS导致最后答案为无解。
如果额外想办法以消耗时间的方法去解决很容易导致TLE(超时)
这里就需要用额外空间的方法去解决设三维数组 c n t i , j , k cnt_{i,j,k} cnti,j,k其中第三维大小为2即布尔下标其中 k t r u e / 1 ktrue/1 ktrue/1时候表示为从起点到 ( i , j ) (i,j) (i,j)的没消耗删除障碍次数的最短路 反之 k f a l s e / 0 kfalse/0 kfalse/0时候表示为从起点到 ( i , j ) (i,j) (i,j)的消耗删除障碍次数的最短路。
最后本次到终点的最短路取两者的最小值即可。
总结思路
普通BFS一次ban掉四个方向各一次并跑BFS取所以答案的最短路最小值
核心代码对应思路
ban掉四个方向各一次并跑BFS
bfs();
for(int i0;i4;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 ( 5 n × m ) O(5n\times m) O(5n×m)
伪代码 代码
#include iostream
#include vector
#include queue
#include deque
#include tuple
#include map
#include cstring
#include algorithm
using namespace std;
const int N 1e310;
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 i1;in;i)cin a[i];//for(int i1;in;i)a[i] a[i];memset(cnt,0x3f,sizeof(cnt));for(int i1;in;i)for(int j1;jm;j)cin a[i][j];
}
inline bool check(int x,int y){return x1 xn y1 ym;
}
void bfs(){int x,y,nx,ny;queuepairint,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 i0;i4;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;queuetupleint,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 i0;i4;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 i0;i4;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;
}
