POJ 2312 Battle City priority queue +BFS

Believe that everyone has played the tank war, this is based on the game design. The tank has to go from the starting point (Y) to the destination (T), the tank cannot go through the steel wall (S), the river (R), can walk in the open space (E), shoot the brick wall (B), shooting the brick wall without walking and it takes one unit of time, walking in the open space also takes one unit of time. Figure out how long it takes the tank to get from the starting point to the destination at least.
Good search question. Due to the difference in the time it takes to get through the brick wall and the open space, it cannot be done using the general BFS search. If you do a deep search with DFS, you will find that the time complexity is very high and will inevitably run over (the maximum is a 300 * 300 graph). This problem can be solved by using improved general search or priority queue + BFS or mnemonic general search.
The first method: improved BFS:
Some nodes take up to 2 units of time, and you have to change them to use BFS, because BFS can only be operated one step at a time, either expanding or breaking the brick wall. So you just check to see if it's a 'B', and if it's a 'B', you have to stop, if it's a 'B', and if it's a 'B' you have to stop, if it's a 'B' you have to stop, and if it's a 'B' you have to continue to expand, which means that some point is expanding a little bit slower, so the point that's coming out of the queue is going to decide which one to do.
From this problem, I also have a deeper understanding of BFS, "the reason why BFS can find the optimal solution quickly is that it operates one step at a time (the operation here is flexible, such as breaking the brick wall in the problem), and the statement in while () is an operation!"

#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
 int x,y,time;
};
int bfs()
{
 int i;
 node you,start,next;
 queue<node>q;
 you.x=sx;
 you.y=sy;
 you.time=0;
 q.push(you);
 visit[sx][sy]=1;
 while(!q.empty())
 {
  start=q.front();
  q.pop();
  if(map[start.x][start.y]=='B')  //This step needs a pause
  {
   start.time++;
   map[start.x][start.y]='E';
   q.push(start);
  }
  else
  {
   for(i=0;i<4;i++)
   {
    next.x=start.x+dir[i][0];     //Search for the next point
    next.y=start.y+dir[i][1];
    if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y])        //To see if the next point is legitimate
     continue;
    next.time=start.time+1;
    if(map[next.x][next.y]=='T')    //Arrive at one's destination
     return next.time;
    visit[next.x][next.y]=1;   //Mark the points that have been passed
    q.push(next);
   }
  }
 }
 return -1;
}
int main(void)
{
 int i,j;
 while(scanf("%d %d",&m,&n)==2)
 {
  if(m==0 && n==0)
   break;
  memset(visit,0,sizeof(visit));     //Initializes the state of each node
  for(i=0;i<m;i++)
  {
   getchar();
   for(j=0;j<n;j++)
   {
    scanf("%c",&map[i][j]);
    if(map[i][j]=='Y')      //Record starting point
    {
     sx=i;
     sy=j;
    }
   }
  }
  printf("%dn",bfs());
 }
 system("pause");
 return 0;
}

The second method is the priority queue +BFS method
Also used the idea of wide search, but when out of the queue to do the processing, the use of priority queue so that the queue to the starting point of the minimum time value of the first out of the queue. This method USES the STL of the priority queue.
First of all, you need to understand the usage rules of priority queues:
By default, the comparison rule of the elements in the priority queue is sorted from large to small according to the value of the elements, that is, the largest element in the queue is always at the head of the queue. Therefore, the largest element in the current queue is not queued according to the first-in first-out principle, but queued. This is similar to sorting the elements in the queue from large to small. Of course, by overloading" < "Operator to redefine the comparison rule.
Overloading" < "Operator function can be written inside the structure, can also be written outside the structure, write outside the structure, remember that the function parameters to use a reference.
The first overload method:

struct node
{
 int x,y;
 int step;
};
priority_queue<node>q;       //By default, the comparison rules for elements in the priority queue are sorted from large to small by their values.
bool operator<(const node &a,const node &b) //Inside the parentheses is const and must be a reference
{
 return a.step>b.step;          //Sort from small to large. Overload the less than sign. Because the default is from big to small
}

The second overload method:

struct node
{
 int x,y;
 int time;  //Define a priority queue
 friend bool operator<(node a, node b)
 {     //From small to large sorting adopt ">" Number; If you want to sort from large to small, use "<" No.
  return a.time> b.time;       //Sort from small to large
 }
};  
priority_queue<node>q;       //By default, the comparison rules for elements in the priority queue are sorted from large to small by their values.

Remember: sort from small to large. > "No; If you want to sort from large to small, use" < "No;

#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
 int x,y,time;  //Define a priority queue
 friend bool operator<(node a, node b)
 {
  return a.time> b.time;       //Sort from small to large
 }
};
int bfs()
{
 int i;
 node you,start,next;
 priority_queue<node>q;
 you.x=sx;
 you.y=sy;
 you.time=0;
 q.push(you);
 visit[sx][sy]=1;
 while(!q.empty())
 {
  start=q.top();  //Queue head pointer is different from normal queue (q.front)
  q.pop();
  for(i=0;i<4;i++)
  {
   next.x=start.x+dir[i][0];     //Search for the next point
   next.y=start.y+dir[i][1];
   if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y])        //To see if the next point is legitimate
    continue;
   if(map[next.x][next.y]=='B')  //Be careful not to be careless here
    next.time=start.time+2;
   else
    next.time=start.time+1;
   if(map[next.x][next.y]=='T')    //Arrive at one's destination
    return next.time;
   visit[next.x][next.y]=1;        //Mark the points that have been passed
   q.push(next);
  }
 }
 return -1;
}
int main(void)
{
 int i,j;
 while(scanf("%d %d",&m,&n)==2)
 {
  if(m==0 && n==0)
   break;
  memset(visit,0,sizeof(visit));     //Initializes the state of each node
  for(i=0;i<m;i++)
  {
   getchar();
   for(j=0;j<n;j++)
   {
    scanf("%c",&map[i][j]);
    if(map[i][j]=='Y')      //Record starting point
    {
     sx=i;
     sy=j;
    }
   }
  }
  printf("%dn",bfs());
 }
 system("pause");
 return 0;
}

The third method: memory to search widely
Unlike the priority queue BFS, which is processed when it is out of the queue, the mnemonic search is processed when it is in the queue. It is not necessary to mark the points in the wide search of memory, just pay attention to the choice in the team. For example, if point A is found, it is necessary to select an adjacent point whose time value is larger than that of point A (cannot be equal) and update the time value of the entry point.

#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
int co,ro,mi,step[305][305];
char map[305][305],visited[305][305];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
typedef struct node
{
 int x;
 int y;
 int time;
}node;
bool judge(int x,int y)
{
 if(x<0||y<0||x>=co||y>=ro)
 {
  return false;
 }
 if(map[x][y]=='S'||map[x][y]=='R')
 {
  return false;
 }
 return true;
}
void  bfs(int a,int b)
{
 int i,x,y,ti;
 node in,out;
 queue<node>que;
 in.x=a;
 in.y=b;
 step[a][b]=0;
 que.push(in);
 while(!que.empty())
 {
  out=que.front();
  que.pop();
  visited[out.x][out.y]=0;   
  for(i=0;i<4;i++)
  {
   x=out.x+dir[i][0];
   y=out.y+dir[i][1];
   if(!judge(x,y))
    continue;
   ti=step[out.x][out.y]+1;
   if(map[x][y]=='B')
    ti++;
   if(step[x][y]<=ti)
    continue;
   step[x][y]=ti;
   if(visited[x][y])
    continue;
   visited[x][y]=1;
   in.x=x;
   in.y=y;
   que.push(in);
  }
 }
}
int main()
{
 int i,j,a,b,c,d;
 while(scanf("%d %d",&co,&ro),co+ro)
 {
  getchar();
  for(i=0;i<co;i++)
   gets(map[i]);
  for(i=0;i<co;i++)
   for(j=0;j<ro;j++)
   {
    if(map[i][j]=='Y')
    {
     a=i;
     b=j;
    }
    if(map[i][j]=='T')
    {
     c=i;
     d=j;
    }
    step[i][j]=999999;       
   }
   memset(visited,0,sizeof(visited));
   visited[a][b]=1;
   bfs(a,b);
   if(step[c][d]!=999999)
    printf("%dn",step[c][d]);
   else
    printf("-1n");
 }
 return 0;
}