找寻小妖 （C++代码）

解题思路:标准的BFS模板题 跑一遍即可

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn 105;
char a[maxn][maxn];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};//DRUL
int path[maxn][maxn],vis[maxn][maxn];
struct st{
	int x,y;
};  
int m,n; 
void bfs(int ax,int ay)
{
	st s,s1,s2;
	queue<st>que;
	s.x=ax;s.y=ay;
	que.push(s);
	memset(vis,0,sizeof(vis));
	memset(path,0,sizeof(path));
	vis[ax][ay]=1;
	while(!que.empty())
	{
		s1=que.front();
		que.pop();
		for(int i=0;i<4;i++)
		{
			int xx=s1.x+dx[i];
			int yy=s1.y+dy[i];
			if(xx>=0&&xx<m&&yy>=0&&yy<n&&vis[xx][yy]==0&&a[xx][yy]!='#')
			{
				path[xx][yy]=path[s1.x][s1.y]+1;
				vis[xx][yy]=1;
				if(a[xx][yy]=='*')
				{
					printf("%d\n",path[xx][yy]);
					return ;
				}
				s2.x=xx;s2.y=yy;
				que.push(s2);
			}
		}
	}
	puts("Impossibility!");
}
int main()
{
	int x1,y1;
    scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++)
		scanf("%s",a[i]);	
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(a[i][j]=='@')
			{
				x1=i;y1=j;
				break;
			}
		}
	}		
	bfs(x1,y1);		
    return 0;
}