2022.02.13

Review today bfs

Problem description

　　 The warriors inadvertently entered the enemy's minefield （ use n That's ok n Matrix representation of columns ,'*' It means that a mine is buried at a certain location ,'-' Indicates that a location is safe ）, They each need to be in the specified number of steps （ One step represents walking to the position adjacent to the current position ） Bypass the mines inside to reach the exit （ The first row, the first space , That is, the coordinates are （0,0） The location of ） To complete the task , Tell you the position of each warrior （x,y） And the specified number of steps s, Please judge whether each warrior can successfully complete the task （1 representative “ can ”,-1 representative “ You can't ”）.

Input format

　　 The first line of input data is an integer n; Line two to line one n+1 Line is n That's ok n Matrix representation of the column mine array （ See input example ）; The first n+2 Go to the last line, and each line is the position of a warrior x、y And the maximum number of steps required to reach the exit s, Three integers are separated by spaces .

Output format

　　 Output the judgment of whether each warrior can successfully complete the task in order （1 representative “ can ”,-1 representative “ You can't ”）, The judgment of each warrior is in one line .

The sample input

5
-----
--*--
-**--
-**--
*-*--
0 1 1
0 4 3
1 1 3
1 4 2
2 0 3
3 0 4
3 3 2
4 1 3

Sample output

1
-1
1
-1
1
1
-1
-1

Data size and engagement

　　1≤n≤500,0≤x≤n-1,0≤y≤n-1,1≤s≤500

#include<iostream>
#include<queue>
using  namespace std;

const int maxn=501;

typedef struct p
{
    int x,y;
}node;

int n;
int X,Y,Z;
char s[maxn][maxn];
int v[maxn][maxn];
int dx[]={-1,0,1,0};// Top left, bottom right 
int dy[]={0,1,0,-1};// Top left, bottom right 

queue<node>q;

void bfs(int a,int b)

{
    node temp;
    v[a][b]=0;
    q.push({a,b});
    while(q.size())
    {
        temp=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx,ny;
            nx=temp.x+dx[i];
            ny=temp.y+dy[i];
            if(nx<0||nx>n-1||ny<0||ny>n-1||v[nx][ny]!=0||s[nx][ny]=='*')
                continue;
            v[nx][ny]=v[temp.x][temp.y]+1;
            q.push({nx,ny});
        }
    }
}                                                          // The key part 

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>s[i][j];
    bfs(0,0);
    while(scanf("%d %d %d",&X,&Y,&Z)!=EOF)
    {
        if(X==0&&Y==0)
            cout<<1<<endl;
        else
        {
            if(v[X][Y]!=0&&v[X][Y]<=Z)
                cout<<1<<endl;
            else
                cout<<-1<<endl;
        }
    }
}

Then there is the mindless problem