All in one 1251 - Fairy Island for medicine (breadth first search)

subject  

Original link http://ybt.ssoier.cn:8088/problem_show.php?pid=1251

【 Title Description 】

Young Li Xiaoyao's aunt is ill , Wang Xiaohu introduced him to Xianling island , Ask fairy sister for fairy pill to save my aunt . Rebellious but filial Li Xiaoyao broke into Xianling island , Overcome thousands of risks and difficulties and come to the center of the island , I found that the magic medicine was placed in the depths of the maze . Maze by M×N Square composition , Some squares contain monsters that can instantly kill Li Xiaoyao , And some squares are safe . Now Li Xiaoyao wants to find the magic medicine as soon as possible , Obviously he should avoid squares with monsters , And through the least squares , And there will be mysterious people waiting for him . Now I ask you to help him achieve this goal .

The figure below It shows an example of a maze and Li Xiaoyao's route to find the magic medicine .

【 Input 】 

There are multiple sets of test data entered . Each set of test data is represented by two non-zero integers M and N Start , Neither is greater than 20.M Indicates the number of rows in the maze , N Indicates the number of maze Columns . Next there is M That's ok , Each row contains N Characters , Different characters represent different meanings :

1)‘@’： The position of young Li Xiaoyao ;

2)‘.’： A square that allows safe passage ;

3)‘#’： A square with monsters ;

4)‘*’： The location of the elixir .

When two zeros are read in a line , End of input .

【 Output 】

For each group of test data , Output one line each , This line contains the minimum number of squares that Li Xiaoyao needs to go through to find the magic medicine ( The count includes the initial position of the box ). If he can't find the magic medicine , The output -1.

【 sample input 】

8 8
[email protected]##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
[email protected]
9 6

.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#[email protected]##
.#..#.
0 0

【 sample output 】

10
8
-1                  

Examine the subject

This problem seems to be solved by deep search , But deep search can only judge whether it can reach , Cannot judge the minimum number of steps

This problem can be said to be in addition to cells （ See blog all in one 1329 cells ） Another broad search template question besides

step

1. Defining variables 、 Structure

struct node{
	int x,y,s;
}; // There must be a semicolon here 
int mk[25][25];// Tag array 
char s[25][25];// Map 
int n,m;
bool flag;// The variable to judge whether it can be reached 
int xy[4][2]={
   {1,0},{-1,0},{0,1},{0,-1}};// Offset 
int res;// Shortest path 
int sx,sy;

2. Define search （BFS） function

void bfs(int x,int y)
{
	mk[x][y]=1;// The passing mark is 1
	queue<node>q;// Define the queue 
	q.push((node){x,y,0});
	while(q.size()) // As long as the queue is not empty, continue to judge 
	{
		node t=q.front();// Take out the team leader 
		q.pop();// Delete team head 
		for(int i=0;i<4;i++)
		{
			int xx=t.x+xy[i][0],yy=t.y+xy[i][1]; // Where to go 
			if(xx>=1 && xx<=n &&yy>=1&&yy<=m&&!mk[xx][yy]&&s[xx][yy]!='#') // If you can walk to 
			{
				if(s[xx][yy]=='*'){// Judge whether it is a fairy medicine 
					flag=1;// Indicates that 
					res=t.s+1;
					return;// return 
				}
				mk[xx][yy]=1;// Otherwise, mark the place you have passed as 1
				q.push((node){xx,yy,t.s+1});// Join the team where you are going 
			}
		}
	}
}

3. The main function

    while(1)// Multiple sets of data input 
	{
		cin>>n>>m;
		memset(mk,0,sizeof(mk));// Because there are many groups , Initialize every time 
		flag=0;
		if(n==0 && m==0) break;// If both inputs are 0, End of input 
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++) // Repeat input 
			{
				cin>>s[i][j];
				if(s[i][j]=='@') sx=i,sy=j; // Mark the starting point 
			}
		}
		bfs(sx,sy);// Start searching from the beginning 
		if(flag) cout<<res<<endl; // If flag It's true , Output steps 
		else cout<<"-1"<<endl;// Otherwise output -1
	}
	return 0;

Take a look at the complete code ：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,s;
}; // There must be a semicolon here 
int mk[25][25];// Tag array 
char s[25][25];// Map 
int n,m;
bool flag;// The variable to judge whether it can be reached 
int xy[4][2]={
   {1,0},{-1,0},{0,1},{0,-1}};// Offset 
int res;// Shortest path 
int sx,sy;
void bfs(int x,int y)
{
	mk[x][y]=1;// The passing mark is 1
	queue<node>q;// Define the queue 
	q.push((node){x,y,0});
	while(q.size()) // As long as the queue is not empty, continue to judge 
	{
		node t=q.front();// Take out the team leader 
		q.pop();// Delete team head 
		for(int i=0;i<4;i++)
		{
			int xx=t.x+xy[i][0],yy=t.y+xy[i][1]; // Where to go 
			if(xx>=1 && xx<=n &&yy>=1&&yy<=m&&!mk[xx][yy]&&s[xx][yy]!='#') // If you can walk to 
			{
				if(s[xx][yy]=='*'){// Judge whether it is a fairy medicine 
					flag=1;// Indicates that 
					res=t.s+1;
					return;// return 
				}
				mk[xx][yy]=1;// Otherwise, mark the place you have passed as 1
				q.push((node){xx,yy,t.s+1});// Join the team where you are going 
			}
		}
	}
}
int main()
{
    while(1)// Multiple sets of data input 
	{
		cin>>n>>m;
		memset(mk,0,sizeof(mk));// Because there are many groups , Initialize every time 
		flag=0;
		if(n==0 && m==0) break;// If both inputs are 0, End of input 
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++) // Repeat input 
			{
				cin>>s[i][j];
				if(s[i][j]=='@') sx=i,sy=j; // Mark the starting point 
			}
		}
		bfs(sx,sy);// Start searching from the beginning 
		if(flag) cout<<res<<endl; // If flag It's true , Output steps 
		else cout<<"-1"<<endl;// Otherwise output -1
	}
	return 0;
}