The previous page takes up too much space. A new chapter is opened again to talk about the problem of BFS seeking the shortest circuit
Note that DFS is not as useful as BFs at this time, because DFS is more suitable for finding all solutions and BFS is suitable for finding the optimal solution
This reminds us again that the idea of topological transformation plays an important role in graph recognition. We need to find the invariance of different graphs during topological transformation

Suppose there is a grid maze composed of n rows and m columns of cells. Each cell is either an open space or an obstacle. How to find the shortest path from the beginning to the end?
Recall the BFs of binary tree. The access order of nodes is exactly the order of the distance from the root node from small to large. Similarly, BFS can be used to traverse the maze in the order of the distance to the starting point (because BFS ensures that the distance from the later traversed point to the starting point is not strictly monotonically increasing)

It is easy to know that if the relationship from the previous step to the next step is regarded as the hierarchical relationship between the ancestors and grandchildren of the tree, a tree can be created. Obviously, a major feature of this tree is that if the row is equal, the local optimization will reach the global optimization, that is, greedy utilization, so that other nodes must have and only have one parent node except the root node, This tree is called the shortest path tree, or BFS tree

Abbott's_Revenge problem solution

Click to view the code

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

const int maxl = 11;

const int maxword = 20+5;
int toward[4][2] = {-1,0,0,1,1,0,0,-1}, dic[maxl][maxl][4][3];

struct Point{
  int x, y;
  Point(int x = 0, int y = 0) : x(x), y(y) {}
};

struct Node{
  int x, y, from;//0 1 2 3 nesw 012 go l f r 
  vector<Point> v[4];
}node[maxl][maxl];

int main() {
//	freopen("test.in", "r", stdin);
//	freopen("test.out", "w", stdout);
  char name[maxword];
  while(scanf("%s", name) == 1 && strcmp(name, "END")) {
  	int sx, sy, ex, ey;
  	char sdic;
  	cin >> sx >> sy >> sdic >> ex >> ey;
  	memset(node, 0, sizeof(node));
  	memset(dic, 0, sizeof(dic));
    int tx, ty;
    while(scanf("%d", &tx) == 1 && tx) {
    	scanf("%d", &ty);
    	node[tx][ty].x = tx;
    	node[tx][ty].y = ty;
    	char buf[10];
		while(scanf("%s", buf)==1 && strcmp(buf, "*")) {
	      int d;
		  switch(buf[0]) {
		  	case 'N': d=0; break;
		  	case 'E': d=1; break;
		  	case 'S': d=2; break;
		  	case 'W': d=3; break;
		  	default: break;
		  }
		  for(int i = 1; i < strlen(buf); i++) {
		  	switch(buf[i]) {
		  	  case 'L': dic[tx][ty][d][0] = 1; break;
			  case 'F': dic[tx][ty][d][1] = 1; break;
			  case 'R': dic[tx][ty][d][2] = 1; break;
			  default : break;
			}
		  }
		}	
	}
		int d;
		switch(sdic) {
		  case 'N': d=0; break;
		  case 'E': d=1; break;
		  case 'S': d=2; break;
		  case 'W': d=3; break;
		  default: break;
		}
		dic[sx][sy][d][1] = 0;
		int sx1 = sx+toward[d][0], sy1 = sy+toward[d][1];
		node[sx1][sy1].x = sx1;
		node[sx1][sy1].y = sy1;
		node[sx1][sy1].v[d].push_back(Point(sx, sy));
		node[sx1][sy1].v[d].push_back(Point(sx1, sy1));
		node[sx1][sy1].from = d;
		queue<Node> q;
		q.push(node[sx1][sy1]);
		vector<Point> ans;
		while(!q.empty()) {
          Node n = q.front();
          q.pop();
          if(n.x == ex && n.y == ey) {
          	ans = n.v[n.from];
			break;
		  }
          int temp = n.from;
		  for(int i = 0; i < 3; i++) {
		  	if(dic[n.x][n.y][temp][i]) {
			  int ndis = (temp+4+i-1)%4, sum = 10;
		  	  int px = n.x+toward[ndis][0], py = n.y+toward[ndis][1]; 
//			  for(int j = 0; j < 3; j++) {
//			  	sum += dic[px][py][ndis][j];
//			  }
			  if(sum) {
			  	Node insert;
			  	insert.x = px;
			  	insert.y = py;
			  	insert.from = ndis;
			  	insert.v[ndis] = n.v[n.from];
			  	insert.v[ndis].push_back(Point(px, py));
			  	q.push(insert);
			  }
		  	  dic[n.x][n.y][temp][i] = 0;	
			}
		  }
		}
		cout << name << endl;
		if(ans.empty()) cout << "  No Solution Possible" << endl;
		else{
		  for(int i = 0; i < ans.size(); i++) {
		  	if(i%10 == 0) cout << "  ";
		  	cout << "(" << ans[i].x << "," << ans[i].y << ")";
		  	if(i%10 == 9) cout << endl;
		    else if(i != ans.size()-1) cout << " ";
		  }
		  if(ans.size()%10) cout << endl;
		}
  }
  return 0;
}

I finally compiled this code by myself, but I still borrowed the debugging of udebug. My own thought is not rigorous enough, but I haven't seen other people's code reference. In addition to simulating the mentality of experts, the idea of this question is relatively simple, that is, don't repeat and don't miss the complete picture. If there is a bfs Road, there will be an answer, otherwise there will be no answer, It should be noted that the storage mode of each node and how to judge the orientation are solved, and this problem will be relatively simple. The difficulty of this problem is the storage and processing of multiple data
It should be noted that in this question, it seems that the display of PE is WA. The author only modified the output format to AC, and can only say UVAOJyyds. Readers here must pay attention to this pit if they are interested