(APP点餐)小D在外玩，回来时想在APP上点KFC，然后回宿舍。他想选择一家KFC，取了食品后尽快回宿舍，忽略取餐时间。地图可看作是n*m的网格，其中有一些不可通过的障碍，小D、KFC、宿舍均可以看做是道路，可以通过，他可穿过多个KFC。小D可以选择上下左右四个方向移动，一次移动算一步。求他取到餐并回到宿舍的最小步数。



输入第一行有两个数n，m.

接下来n行，每行包含m个字符，表示地图。

“S”表示小D初始位置，

“E”表示宿舍位置

“#”表示障碍物

“.”表示道路

“K”表示KFC

下面的程序已采用宽度优先搜索的算法完成这个问题，试补全程序。

#include<bits/stdc++.h>


# define fi first


# define se second


using namespace std;


const int MAXN=1e3+10;


const int INF = 0x313f3f3f;


typedef pair<int,int> P;


char s[MAXN][MAXN];


int n,m;


int dir[2][4]= {{1,-1,0,0},{0,0,1,-1}};


int dis[2][MAXN][MAXN];





void bfs(int p,int a,int b){


	memset(dis[p],INF,sizeof(dis[p]));


	dis[p][a][b]=0;


	queue<pair <P,int> > q;


	q.push({{a,b},0});


	while(!q.empty()) {


		int x=q.front().fi.fi,


		    y=q.front().fi.se,


		    d=q.front().se;


		q.pop();


		for(int i=0; i<4; i++)	{


			int dx=x+dir[0][i],


			    dy=y+dir[1][i];


			if (dx<1||dy<1||dx>n||dy>m||s[dx][dy]=='#')


				continue;


			if(___(1)___)	{


				___(2)___;


				___(3)___;


			}


		}


	}


}





int main(void)


{


	while(scanf("%d%d",&n,&m)!=EOF)	{


		int ans=INF;


		scanf("%d%d",&n,&m);


		for (int i=1; i<=n; i++)


			scanf("%s",s[i]+1);


		for(int i=1; i<=n; i++)


			for (int j=1; j<=m; j++)


				if(s[i][j]=='S')


					bfs(0,i,j);


				else if(s[i][j]=='E')


					___(4)___;


		for(int i=1; i<=n; i++)


			for (int j=1; j<=m; j++)


				if(s[i][j]=='K')


					ans=___(5)___;


		if(ans==INF)


			ans=-1;


		printf("%d\n",ans);


	}


	return 0;


}

选择题