Thinking and practice of program design

A.Maze

Title Description:

There is a map in Dongdong. I want to find Meizhi through the map. The map shows that 0 means you can walk, 1 means you can't walk, the upper left corner is the entrance, and the lower right corner is Meizhi. These two positions are guaranteed to be 0. Now that you know the map, it's not difficult for Dongdong to find Meizhi. Please make a program to write the shortest route for Dongdong to find Meizhi.

Input :
The input is a 5 × 5 two-dimensional array, which only consists of 0 and 1 numbers, representing the normal map.
Output :
Output several lines to represent the coordinates of the shortest path from the upper left corner to the lower right corner in turn, with the format shown in the example. Data guarantees a unique solution.

Sample Input:
0 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 1 0
Sample Output:
(0, 0)
(1, 0)
(2, 0)
(3, 0)
(3, 1)
(3, 2)
(2, 2)
(1, 2)
(0, 2)
(0, 3)
(0, 4)
(1, 4)
(2, 4)
(3, 4)
(4, 4)
Hint:
The coordinate (x, y) indicates the row X and column y, the number of which starts from 0 and takes the upper left corner as the origin.
Also note that there should be a space after the comma separating the coordinates in the output.

Thought analysis:

This and maze mouse problem is a principle. There are two ways to search the path: dfs combining stack and bfs combining queue. But in this topic, the shortest path is required, so I will choose width search here. Use a reach array to mark, that is, mark the passing points to avoid returning to the original road. Another key point is that I need to record the points of the path, so define the structure point to represent the coordinates x,y of a point, and then define a two-dimensional path array of point type. The index is x,y of the point stored in path. In this way, when we finish bfs, I can go back to the path point one by one through the end point, that is, the path.

Code implementation:
#include<cstdio>
#include<queue>
using namespace std;
struct point//Store coordinates on the way
{
 int x;
 int y;
}p[5][5];//Two dimensional array. If it meets the following judgment conditions, it will join the team
int main()
{
    //Input labyrinth
	int k=0;//Store the corresponding index of coordinates in p 
	int reach[5][5];//Mark. If you go through this point, mark this point 
	int maze[5][5];
	for(int i=0;i<5;i++)
	    for(int j=0;j<5;j++)
	    {
		    scanf("%d",&maze[i][j]);
		    reach[i][j]=0;//At the beginning, none of these points passed by 
		    p[i][j].x=i;
		    p[i][j].y=j;
		    //p[k].x=i;
		    //p[k++].y=j;
		}
	//Start bfs
	//int road[25]; / / record the points on the path
	int dx[]={0,0,1,-1};//x direction 
	int dy[]={1,-1,0,0};//y direction
	queue<point> q;
	q.push(p[0][0]);//The first position in the maze must be 0. You can join the team 
    reach[0][0]=1;//sign 
	//printf("(%d,%d)",p[0][0].x,p[0][0].y); / / output the coordinates of the first point 
	point path[5][5];//Store origin to previous point of a point 
	 for(int i=0;i<5;i++)//Path initialization
        for(int j=0;j<5;j++)
        {
            path[i][j].x=0;
            path[i][j].y=0;
        }
	//int pathindex=0;
	while(!q.empty())
	{
		point temp=q.front();
	//	printf("the current pop's point (% d,%d)\n",temp.x,temp.y); / / the queued ones can output???? 
		q.pop();
		//bool ifstop=false;
		for(int i=0;i<4;++i)//Check in all four directions to see if you can check it by right, left, down and up 
		{
			int x=temp.x+dx[i],y=temp.y+dy[i];//
			//printf("x%d,y%d\n",x,y);
		//	printf("corresponding to maze%d\n",maze[x][y]);
		    if(x>=0&&x<5&&y>=0&&y<5&&!maze[x][y]&&!reach[x][y])
			{//Judgment condition: the coordinate does not exceed the boundary, the position is not 1 and the point has not been passed
			    path[x][y].x=temp.x;
			    path[x][y].y=temp.y;//The precursor node of this point is stored in the queue, and the precursor node values in four directions are only stored once 
				reach[x][y]=1;//The mark indicates that this point has passed
				q.push(p[x][y]);//Join the team
			}
		} 
	}
	point  out[25];//Storing the output points is the shortest path
	int w=0;
	out[0].x=4;
	out[0].y=4;    
	//Start at the end, one by one, and find the path in reverse
    while(out[w].x!=0||out[w].y!=0)
    {
    	w++;
		out[w].x=path[out[w-1].x][out[w-1].y].x;
		out[w].y=path[out[w-1].x][out[w-1].y].y;
	}
	printf("(0, 0)\n");
	for(int i=w-1;i>0;i--)//When getting out, the path is stored from the end point, so the output should be reversed naturally
	    printf("(%d, %d)\n",out[i].x,out[i].y);
	printf("(4, 4)");
	return 0; 
}
Summary of question A:

This problem can be solved by grasping two key points, combining with the width search of queue, using array to store the previous point.

B- Pour Water

Title Description:

Water pouring problem "fill A" means to fill cup A, "empty A" means to empty cup A, "pour A B" means to pour water of A into cup B and fill cup B or empty cup A.
Input:
The input contains multiple sets of data. Each group of data input A, B, C data range 0 < A < = B, C < = B < = 1000, A and B mutual quality.
Output:
The output of your program will consist of a series of instructions. These outputs will cause any tank to contain exactly C units of water. The last line of output for each set of data should be "success.". The output line starts at column 1 and should not have blank lines or any trailing spaces.
Sample Input:
2 7 5
2 7 4
Sample Output:
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success

Notes:
If your output is different from Sample Output, it doesn't matter. The answer to a certain "A B C" question is multi-resolution. You can't judge whether your program is correct or not by standard text comparison. Therefore, SPJ (Special Judge) program is used to determine whether the code you write is correct.

Thought analysis:

The first reaction to get this question is very silly, but since it's this week's experiment, it must have something to do with bfs.
There are six kinds of water pouring operations: filling a, filling B, reversing a to B until a is empty or B is full, reversing B to a until B is empty or a is full, making a empty or B is empty, so I define the structure status and the members represent the water margin and operation op in a and B after the operation op is performed. The two-dimensional array reach of status type is defined to mark, and the index of reach represents the existing water quantity in cups a and B, so as to prevent backwater from returning to the original state. After that, I still use bfs and queue. Only when the queue is not empty, I will leave the queue in a state. Then I will perform the above six operations in this state. As long as the reach[a][b] corresponding to the water margin a and B of the two water cups is not marked after the operation, I will enter the state after the operation into the queue again. Over and over again, know that out of the state of any cup of water to meet the problem.
In addition, how to record the operation here? Every time I enter the team, I record the operation of my trip. In the next cycle, I will leave the team in this operation state, and I will add my operation string in this out of team state. After the cycle, I record the water pouring operation step, which is the "path" of water pouring.
(there are also detailed comments in the code)

Code implementation:
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;

struct status
{
	int a,b;//A. B. water quantity of cup after operation op
	string op;
	
	status(){}//Nonparametric construction without semicolon 
	status(int thea,int theb,string theop)
	{
		a=thea;
		b=theb;
		op=theop;
	}
	status& operator=(status &ss)
	{
		a=ss.a;
		b=ss.b;
		op=ss.op;
		return *this;
	}
};
int reach[1000][1000];//sign


queue<status> q;
int main()
{
	int a,b,c;
	queue<status> q;
//	string str1="fa",str2="fb",str3="ea",str4="eb",str5="pa",str6="pb";
	while(~scanf("%d%d%d",&a,&b,&c))//input
	{
	    while(!q.empty())//Clear queue 
	        q.pop();
		memset(reach,0,sizeof(reach));//Initialization
		q.push(status(0,0,string()));//Initial situation of starting point
	    reach[0][0]=1;//Starting point already visited
	    if(a==c)
	    {
	        printf("fill A\nsuccess\n");
	        break;
	        //return 0;
	    }
	    if(b==c)
	    {
	        printf("fill B\nsuccess\n");
	        break;
	        //return 0;
	    }
	 
	    while(!q.empty())
	    {
		   int aa=q.front().a;
		   int bb=q.front().b;
		   string opp=q.front().op;
		   q.pop();
		   //Judge whether the current cup has met the question b > = C, then you can find the right one in the big cup B
		 //  printf("bb%d c%d\n",bb,c);
		   // printf("aa%d bb%d\n",aa,bb);
		   if(bb==c) //Every time you leave the team, you have to judge whether the current status has met the question
		   {
		      // for(int i=0;i<opp.size();i++)
		        //   printf("%c",opp[i]);
		        //printf("\n");
			   for(int k=0;k<opp.size();k++)
		       {
		       	    //string temp=opp.substr(k,k+2);
		       	      //  printf("%c%c",temp[0],temp[1]);
		       	    //printf("\n");
		       	    //For the convenience of processing, a, B, C, D, e and F are used to represent the six states respectively
					if(opp[k]=='a')
		       	        printf("fill A\n");
		       	    if(opp[k]=='b')
		       	        printf("fill B\n");
		       	    if(opp[k]=='c')
		       	        printf("empty A\n");
		       	    if(opp[k]=='d')
		       	        printf("empty A\n");
		       	    if(opp[k]=='e')
		       	        printf("pour B A\n");
		       	    if(opp[k]=='f')
		       	        printf("pour A B\n");   
			   }
			   
			   printf("success\n");
			   break;
		//	   return 0;
		   }
		  // else
		      // continue;
		 
		   //Let's join the team
		   if(!reach[a][bb])//Fill up a.
		   {
			   // printf("%d %d\n",a,bb);
				q.push(status(a,bb,opp+'a'));
			    reach[a][bb]=1;//Marking 
		   }
		   if(!reach[aa][b])//Fill up b.
		   {
		    	//printf("%d %d\n",aa,b);
				q.push(status(aa,b,opp+'b'));
			    reach[aa][b]=1;
		   }
		   if(!reach[0][bb]) //Emptying A 
		   {
		    	//printf("%d %d\n",0,bb);
				q.push(status(0,bb,opp+'c'));
			    reach[0][bb]=1;
	 	   }
		   if(!reach[aa][0]) //Emptying B 
		   {
		    	//printf("%d %d\n",aa,0);
				q.push(status(aa,b,opp+'d'));
			    reach[0][bb]=1;
		    } 
		    int after_pour=aa+bb;
		    if(after_pour>a)//If it is inverted, it will exceed the capacity, so take the capacity of A 
		        after_pour=a;
		    if(!reach[after_pour][aa+bb-after_pour])//Pour water into A
		    {
			    //printf("%d %d\n",after_pour,aa+bb-after_pour);
				q.push(status(after_pour,aa+bb-after_pour,opp+'e'));
			    reach[after_pour][aa+bb-after_pour]=1;
		    }
		    after_pour=aa+bb;
		    if(after_pour>b)
		        after_pour=b;
		    if(!reach[aa+bb-after_pour][after_pour])
		    {
			    //printf("%d %d\n",aa+bb-after_pour,after_pour);
				q.push(status(aa+bb-after_pour,after_pour,opp+'f'));
				reach[aa+bb-after_pour][after_pour]=1;
		    }	 
	   }
	   //while
    }
    return 0;
//	status out[1000];

}
Summary of question B:

I think the difficulty of this problem lies in whether we can find that bfs can be used to deal with it. At first glance, the connection between bfs and the graph is very small. However, after using the water in two cups to represent the points in the graph, the model of the graph is very clear, and then using bfs and the queue is very simple. The way to record the path of this question is more ingenious. My previous practice must be to record the water quantity and operation of the previous state of the current state like that of the maze. Such code is obviously more redundant.

Published 3 original articles, won praise 0, visited 14
Private letter follow

Posted on Tue, 03 Mar 2020 19:59:50 -0800 by gumby51