A - maze problem

Problem 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.

problem analysis

1. The structure weizi stores the coordinates of the current position. And set dx, dy array to represent the change of position.
2.bfs, establish a queue, traverse each direction in the loop, and judge whether the newly added position meets three conditions:
(1) . within the boundary
(2) . not visited
(3) . displayed as reachable on the map.
Enter the team if you meet. The next loop takes a state from the queue head to expand.
[among them, if the VIS array records arrive, I also use some changes to make vis not only indicate whether the state has been extended, but also indicate the last node of the state, which is related to the value of VIS]
3. Use vis array to find the parent state of the target state and store it in the stack
4. Output the status in the stack in order.

Code

#include<iostream>
using namespace std;
#include<queue>
#include<stack>
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int tu[5][5];
struct weizi
{
	int x;
	int y; 
}; 
queue<struct weizi*> q;
stack<struct weizi*> g;
void bfs()
{
	int x=0;
	int y=0;
	int vis[5][5];
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			vis[i][j]=0;
	struct weizi *currentnode,*newnode;
	currentnode=new struct weizi;
	currentnode->x=0;
	currentnode->y=0;
	q.push(currentnode);
	bool pan=true;
	vis[0][0]=100; 
	while(q.size()!=0)
	{
		currentnode=q.front();
		q.pop();
		if(currentnode->x==4&&currentnode->y==4)
			break;
		for(int i=0;i<4;i++)
		{
			x=currentnode->x+dx[i];
			y=currentnode->y+dy[i];
			
			if(x>=0&&y>=0&&x<=4&&y<=4&&vis[x][y]==0&&tu[x][y]==0)
			{
				newnode=new struct weizi;
				newnode->x=x;
				newnode->y=y;
				q.push(newnode);
				vis[x][y]=currentnode->x*10+currentnode->y+1;
				if(x==4&&y==4)
				pan=false;
			}
		}
	}
	x=4;y=4;
	int shu;
	while(vis[x][y]!=100)
	{
		newnode=new struct weizi;
		newnode->x=x;
		newnode->y=y;
		g.push(newnode);
		shu=vis[x][y];
		y=shu%10-1;
		x=shu/10; 
	}
	cout<<"("<<0<<", "<<0<<")"<<endl; 
	
	while(!g.empty())
	{
		currentnode=g.top();
		g.pop();
		cout<<"("<<currentnode->x<<", "<<currentnode->y<<")"<<endl; 
	}
	
	
}
int main()
{
	
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>tu[i][j];
	
	bfs();
 } 

Problems encountered

I think my code is a bit redundant, like queue and stack. But I didn't figure out how to change it

B - water pouring

Problem 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.

problem analysis

1. The structure condition contains the state of two bottles a and b.
2.bfs: to establish a queue, first add (0, 0) and status. Then I went into the loop. I directly used six if statements to roughly judge whether this extension can be carried out. If it can, I will carry out this operation and add the newly generated new node to the queue.
Conditions to be met my settings are: (A, B, C are the input data)
fill A: a!=A；
pour A B: a!=0&&b!=B；
empty A: a!=0；
In the same way, remove some unqualified conditions in advance, and at the same time judge whether such operation has occurred on judge [].
3. At the same time of bfs, some arrays are used to store the current operation [], and the position of the last parent []. When bfs finds the target state and exits the loop. Use these two arrays to trace how they arrived. And the experienced operations are converted into numbers and stored in the array jilu []. At last, we can output them in reverse order

Code

#include<iostream>
using namespace std;
#include<queue>
#include<string.h>
//1..fillA/2..fillB/3..pourAtoB/4..pourBtoA/5..emptyA/6..emptyB
struct condition
{
	int a;
	int b;
};
int A,B,C;
int parent[10000];
int operation[10000];
int jilu[10000];

queue<struct condition*> q;

struct condition* FillA(struct condition* current)
{
	struct condition* newnode=new struct condition;
	newnode->a=A;
	newnode->b=current->b;
	return newnode;
}
struct condition* FillB(struct condition* current)
{
	struct condition* newnode=new struct condition;
	newnode->b=B;
	newnode->a=current->a;
	return newnode;
}
struct condition* PourAtoB(struct condition* current)
{
	struct condition* newnode=new struct condition;
	if(current->a+current->b>B)
	{
		newnode->a=current->a-(B-current->b);
		newnode->b=B;
	}
	else
	{
		newnode->b=current->a+current->b;
		newnode->a=0;
	}
	return newnode;
}
struct condition* PourBtoA(struct condition* current)
{
	struct condition* newnode=new struct condition;
		if(current->a+current->b>A)
	{
		newnode->b=current->b-(A-current->a);
		newnode->a=A;
	}
	else 
	{
		newnode->a=current->a+current->b;
		newnode->b=0;
	}
	return newnode;
}
struct condition* emptyA(struct condition* current)
{
	struct condition* newnode=new struct condition;
	newnode->a=0;
	newnode->b=current->b;
	return current;
}
struct condition* emptyB(struct condition* current)
{
	struct condition* newnode=new struct condition;
	newnode->b=0;
	newnode->a=current->a;
	return newnode;
}
void bfs()
{
	int judge[1000000];
	memset(judge,0,sizeof(judge));
	struct condition *currentnode,*newnode;
	newnode=new struct condition;
	newnode->a=0;
	newnode->b=0;
	q.push(newnode);
	int shu=0,now=-1;
	judge[0]=1;
	while(q.size()!=0&&shu<=10000)
	{
		currentnode=q.front();
		q.pop();
		now++;
		if(currentnode->a!=A)
		{
			newnode=FillA(currentnode);
			if(judge[newnode->a*1000+newnode->b]==0)
			{
				judge[newnode->a*1000+newnode->b]=1;
				q.push(newnode);
				shu++;
				operation[shu]=1;
				parent[shu]=now;
			}	
			//cout<<"1   "<<shu<<"    "<<newnode->a<<"  "<<newnode->b<<endl;
		}
		if(currentnode->b!=B)
		{
			newnode=FillB(currentnode);
			if(judge[newnode->a*1000+newnode->b]==0)
			{
				judge[newnode->a*1000+newnode->b]=1;
				q.push(newnode);
				shu++;
				operation[shu]=2;
				parent[shu]=now;
			}
			//cout<<"2   "<<shu<<"    "<<newnode->a<<"  "<<newnode->b<<endl;
		}
		if(currentnode->a!=0&&currentnode->a+currentnode->b!=0)
		{	
			newnode=emptyA(currentnode);
			if(judge[newnode->a*1000+newnode->b]==0)
			{
				judge[newnode->a*1000+newnode->b]=1;
				q.push(newnode);
				shu++;
				operation[shu]=5;
				parent[shu]=now;
			}	
			//cout<<"5   "<<shu<<"    "<<newnode->a<<"  "<<newnode->b<<endl;
		}
		if(currentnode->b!=0&&currentnode->a+currentnode->b!=0)
		{
			newnode=emptyB(currentnode);
			if(judge[newnode->a*1000+newnode->b]==0)
			{
				judge[newnode->a*1000+newnode->b]=1;
				q.push(newnode);
				shu++;
				operation[shu]=6;
				parent[shu]=now;
			}
			//cout<<"6   "<<shu<<"    "<<newnode->a<<"  "<<newnode->b<<endl;
		}
		if(currentnode->a!=0&&currentnode->b!=B&&currentnode->a+currentnode->b!=0)
		{
			newnode=PourAtoB(currentnode);
			if(judge[newnode->a*1000+newnode->b]==0)
			{
				judge[newnode->a*1000+newnode->b]=1;
				q.push(newnode);
				shu++;
				operation[shu]=3;
				parent[shu]=now;
			}
			//cout<<"3   "<<shu<<"    "<<newnode->a<<"  "<<newnode->b<<endl;
			if(newnode->b==C)
				break;
			if(newnode->a==C)
				break;
		}
		if(currentnode->b!=0&&currentnode->a!=A&&currentnode->a+currentnode->b!=0)
		{
			newnode=PourBtoA(currentnode);
			if(judge[newnode->a*1000+newnode->b]==0)
			{
				judge[newnode->a*1000+newnode->b]=1;
				q.push(newnode);
				shu++;
				operation[shu]=4;
				parent[shu]=now;
			}
			//cout<<"4   "<<shu<<"    "<<newnode->a<<"  "<<newnode->b<<endl;
			if(newnode->a==C)
				break;
			if(newnode->b==C)
				break;
		}	
	}
	int current=shu;
	int i=0;
	while(current!=0)
	{
		jilu[i]=operation[current];
		current=parent[current];
		i++;	
	}
	for(int j=i-1;j>=0;j--)
	{
		switch(jilu[j])
		{
			case 1:
				{
					cout<<"fill A"<<endl;
					break;
				}
			case 2:
				{
					cout<<"fill B"<<endl;
					break;
				}
			case 3:
				{
					cout<<"pour A B"<<endl;
					break;
				}
			case 4:
				{
					cout<<"pour B A"<<endl;
					break;
				}
			case 5:
				{
					cout<<"empty A"<<endl;
					break;
				}
			case 6:
				{
					cout<<"empty B"<<endl;
					break;
				}
			
		}
	}
		cout<<"success"<<endl;
		while(!q.empty())q.pop();
}

int main()
{
	
	while(cin>>A>>B>>C)
	{
		bfs();
	}
	return 0;
}

Problems encountered

1. At the beginning of writing, it is not considered to judge whether the current state has appeared, but to judge what a situation is in each situation. It may lead to incorrect answers.
2. The memset function didn't work well (the following size is wrong), which was quickly solved.
3. There has been a dead cycle, but the main idea is right. After careful inspection, it is found that when I pass parameters, I modify the contents of the curent pointer instead of just assigning a value to the newnode. And it hasn't added weight, so the elements of joining the team have been circulating.