题面

我们把球场看作一个N*M的网格，其中有一些格子是对方的防守球员，另一些格子是无人防守的空地。用1表示此处有防守球员，0表示此处无人防守。阿韦罗的过人本领为K，说明他最多可以带球经过K个有防守球员的格子。如果路径上有超过K个防守球员，阿韦罗就会选择回传或者跳水。

现在给出阿韦罗所在的地点(X,Y)和需要到达的地点(P,Q)，他希望可以找出一条路径，以最少的步数将球带到目的地。每步可以往上、下、左、右四个方向中任意一个方向走一格。

输入格式

第一⾏输入七个正整数N，M，X，Y，P，Q，K，两两之间用一个空格隔开，含义如题所述。

接下来输入一个N*M的01矩阵表示球场地图。

输出格式

输出一个整数，表示到达目的地最少的步数。题目保证输入数据有解。

数据范围

对于40%的数据，K=0。

对于100%的数据，0<N,M,K<=100，0<X，P<=N，0<Y，Q<=M。

思路

bfs 求最短路径。

代码(60pts)

#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node
{
	int x,y,num,step;
};
int n,m,k;
int sx,sy,ex,ey;
char mp[105][105];
bool vis[105][105];
void bfs()
{
	queue<node> q;
	q.push({sx,sy,0,0});
	vis[sx][sy]=1;
	while(!q.empty())
	{
		node t=q.front();
		q.pop();
		int x=t.x,y=t.y; 
		bool flag=0;
		for(int i=0;i<4;i++)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty]) continue;
			if(t.num+(mp[tx][ty]-'0')>k) continue;
			vis[tx][ty]=1;
			q.push({tx,ty,t.num+(mp[tx][ty]-'0'),t.step+1});
			if(tx==ex&&ty==ey)
			{
				cout << t.step+1 << "\n";
				flag=1;
				break;
			}
		}
		if(flag) break;
	}
}
int main()
{
	cin >> n >> m >> sx >> sy >> ex >> ey >> k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) cin >> mp[i][j];
	bfs();
    return 0;
}

求助qwq（悬关）