5611: 【J1】【搜索】网格寻路

题目描述

给你一个 n * m 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您最多可以消除 k 个障碍物，请找出从左上角 (1, 1) 到右下角 (n, m) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。

输入

第一行，两个整数n，m

接下来的n行，每行输入一个整数0或1

第n+2行一个整数k，表示最多可以消除的障碍物数目

输出

输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

5 3
0 0 0
1 1 0
0 0 0
0 1 1
0 0 0
1

样例输出

6

Code:

#include
using namespace std;
struct node{
	int x,y,s,rk;
};
int n,m,a[55][55],k;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool vis[55][55][100];
int bfs(){
	queueq;
	node sp={1,1,0,k};
	q.push(sp);
	while(!q.empty()){
		node p=q.front();
		q.pop();
		if(p.x==n&&p.y==m){
			return p.s;
		}
		for(int i=0;i=1&&ty>=1&&tx=1&&ty>=1&&txn>>m;
    for(int i=1;ia[i][j];
		}
	}
	cin>>k;
	k=min(k,n+m-3);
	vis[1][1][k]=1;
	cout