1.12 learning summary

Today's main learning content is to see the related concepts of trees and several methods of building trees . Tell the truth , After reading it for a day, I didn't particularly understand . All I know is to use . Linked list and structure to realize one to many operation . It's not like a linear table . So I don't know what to sum up today . But I can still feel , The function of tree is very powerful . So more complex data access . In that case, I will make one today . Let's solve the problem . Also review the contents of the search by the way .

The title is as follows ,

  This is a slightly adapted maze problem . He is on a common maze problem , Added a transfer point setting . Originally, the maze problem used DFS and BFS It's quite easy to solve .  But on this issue , What the title asks for , Is the quickest way to get there . So I chose BFS To carry out . The general maze problem is to change a variable Store coordinates , And determine whether this coordinate conforms to . Conditions to determine the path . And for the transfer point ,  I just need to design a function . The value at this coordinate , If it's a transfer point , Let him input this function . And then traverse the entire map . To find another transfer point . The condition is that both values are the same . But the coordinates are different . Then change the value of this variable to the coordinates of another transfer point . Then you can turn this problem into a common maze problem . The rest of the steps are and BFS The template is the same . The specific code is as follows . Of course, my method is still more violent . Because I have to traverse the entire array every time I judge the transfer point . In this case , If there are too many transfer points or the map is large , It is possible that the time limit is exceeded .  I think for a long time , I didn't think of any algorithm that could optimize a lot .  The specific code is as follows ,

  #include<stdio.h>
 #include<queue> 
 #include<stdlib.h>
 #include<iostream>
 using namespace std;
  int n,m; int x1,y4,x3,y3,s;  
  char map[301][301];
  int map1[301][301];
  int dx[4]={0,0,1,-1};
  int dy[4]={1,-1,0,0};
  int x2,y2; 
 struct g{                                           
 	int x,y,step;
 	
 };
 queue<g> p;
  void l(int &a,int &b){
  	for(int i=1;i<=n;i++){
  		for(int j=1;j<=m;j++){
  			if(map[i][j]==map[a][b] && (i!=a || j!=b))
  				{a=i,b=j;return;}
  		}
  	}
  }
  int main(){
  		scanf("%d %d",&n,&m);
  	for(int i=1;i<=n;i++){
  		for(int j=1;j<=m;j++)
  			{ cin>>map[i][j];
  			if(map[i][j]=='@') x1=i,y4=j;
  			if(map[i][j]=='=') y3=i,x3=j;}
 			 }
  	 	p.push(g{x1,y4,0}); map1[x1][y4]=1;
 	   	g t1;
 	   	int x2,y2;
 	   	while(!p.empty()){
 	   	t1 = p.front();
 	   		if(map[t1.x][t1.y]=='=') {s=t1.step;
 	  		 break;}
 	   		if(map[t1.x][t1.y]>='A' && map[t1.x][t1.y]<='Z'){ 
 	   		    l(t1.x,t1.y);
 	   		}
 	   		for(int i=0;i<4;i++){
 	   			x2=t1.x+dx[i]; y2=t1.y+dy[i];
 	   			if(x2>=1&&x2<=n&&y2>=1&&y2<=m && map1[x2][y2]!=1 && map[x2][y2]!='#'){
 	   				map1[x2][y2] = 1;
 	   				p.push(g{x2,y2,t1.step+1});
 	   			}
 	   		}
 	   		p.pop();
 	   		
 	   	}
  	printf("%d",s);
  	return 0;
  }

Today's learning summary , That's it .  We must learn more tomorrow .