A-Maze

Topic content
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 format
The input is a 5 × 5 two-dimensional array, which only consists of 0 and 1 numbers, representing the normal map.

Output format
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.

Example

Remarks
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.
　　
Solving problems
In the classic Maze problem, at first glance, Maze is really regarded as "sister paper". The idea is bfs, which records the parent point of the point when traversing to a certain point, so as to use it as the final output.
If you don't say much, go straight to the code:

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int map[5][5];

struct point 
{
	int x, y;

}pre[5][5];

queue<point> q;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void bfs()
{
	while (!q.empty()) q.pop();

	point start;
	start.x = 0, start.y = 0;

	q.push(start);
	pre[0][0].x = 0; pre[0][0].y = 0;

	while (!(q.front().x == 4 && q.front().y == 4))
	{
		point from = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			point to;//to for the next step 
			to.x = from.x + dx[i];
			to.y = from.y + dy[i];

			if (to.x < 0 || to.x >= 5 || to.y < 0 || to.y >= 5) continue;

			if (map[to.x][to.y] || pre[to.x][to.y].x != -1) continue;

			q.push(to);
			pre[to.x][to.y].x = from.x; pre[to.x][to.y].y = from.y;
		}
	}
}

void print(int x, int y)
{
	if (pre[x][y].x != x || pre[x][y].y != y)
	{
		print(pre[x][y].x, pre[x][y].y);
	}

	cout << '(' << x << ", " << y << ')' << endl;//First in second out output path~
}

int main()
{
	memset(pre, -1, sizeof pre);

	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
			cin >> map[i][j];
	}
	
	bfs();
	print(4, 4);

	return 0;
}

B-Water pouring

Topic content
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.
It's really the classic problem of pouring 4 water from 35 cups, but this time it requires any pair of cups.

Input format
The input contains multiple sets of data. Each group of data input A, B, C data range 0 < A < = B, C < = B < = 1000 and A and B are mutually prime (necessary conditions)

Output format
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.

Example

fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success

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

Solving problems
In fact, if you think about it a little bit, you will find that there are six options for each operation:

• Fill A up
• Fill B up
• Empty the A.
• Empty the B.
• Pour water from A into B
• Pour water from B into A

In this way, we only need bfs to traverse each layer of selection.

A feasible pruning:

• When A is empty, it cannot be emptied or emptied into B
• When A is full, it can't be filled or A can't be filled from B
• The same principle of AB exchange above

The following is my code, can correctly output but WA, Xinsai:

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>

using namespace std;

const string operation[8] = { "success","fill A","fill B","empty A","empty B","pour A B","pour B A","start" };

int limitA, limitB, target;//A B C
bool visit[1001][1001];

struct State
{
	int curA, curB;
	int opnum;
};

struct Node
{
	int opnum;
	Node* father;
	Node();
	Node(const int& f_op)
	{
		this->opnum = f_op;
		this->father = NULL;
	}
	Node(const int &f_op, Node*& thefather)
	{
		this->opnum = f_op;
		this->father = thefather;
	}
};

queue<State>sq;
queue<Node*>nq;


State fillA(State &s)
{
	State next;
	next.curA = limitA;
	next.curB = s.curB;
	next.opnum = 1;
	return next;
}

State fillB(State &s)
{
	State next;
	next.curA = s.curA;
	next.curB = limitB;
	next.opnum = 2;
	return next;
}

State eraseA(State &s)
{
	State next;
	next.curA = 0;
	next.curB = s.curB;
	next.opnum = 3;
	return next;
}

State eraseB(State &s)
{
	State next;
	next.curA = s.curA;
	next.curB = 0;
	next.opnum = 4;
	return next;
}

State pourAB(State &s)
{
	State next;
	int sub = limitB - s.curB;
	if (s.curA > sub)
	{
		next.curA = s.curA - sub;
		next.curB = limitB;
	}
	else
	{
		next.curA = 0;
		next.curB += s.curA;
	}
	next.opnum = 5;
	return next;
}

State pourBA(State &s)
{
	State next;
	int sub = limitA - s.curA;
	if (s.curB > sub)
	{
		next.curB = s.curB - sub;
		next.curA = limitA;
	}
	else
	{
		next.curB = 0;
		next.curA += s.curB;
	}
	next.opnum = 6;
	return next;
}

Node *bfs(State start)
{
	sq.push(start);
	visit[start.curA][start.curB] = true;
	Node* n_start = new Node(7);
	nq.push(n_start);
	while (true)
	{
		State now = sq.front();
		sq.pop();
		int A = now.curA;
		int B = now.curB;
		int Op = now.opnum;
		for (int i = 1; i <= 6; i++)
		{
			State snext;
			snext.curA = snext.curB = 0;
			snext.opnum = 8;
			switch (i)
			{
			case 1:
				if (A == limitA) break;
				snext = fillA(now);
				break;
			case 2:
				if (B == limitB) break;
				snext = fillB(now);
				break;
			case 3:
				if (A == 0) break;
				snext = eraseA(now);
				break;
			case 4:
				if (B == 0) break;
				snext = eraseB(now);
				break;
			case 5:
				if (A == 0) break;
				snext = pourAB(now);
				break;
			case 6:
				if (B == 0) break;
				snext = pourBA(now);
				break;
			default:
				break;
			}

			if (snext.opnum == 8) continue;
			if (visit[snext.curA][snext.curB]) continue;

			sq.push(snext);
			visit[snext.curA][snext.curB]=true;
			Node* temp = new Node(snext.opnum, nq.front());
			nq.push(temp);

			if (snext.curA == target || snext.curB == target)
			{
				return temp;
			}
		}
		
		nq.pop();
	}

}

void print(Node* n)
{
	if (n->father->opnum != 7)
		print(n->father);
	cout << operation[n->opnum] << endl;
}


int main()
{

	while (cin >> limitA >> limitB >> target)
	{
		while(!sq.empty()) sq.pop();
		while(!nq.empty()) nq.pop();
		memset(visit, false, sizeof visit);
		State start;
		start.curA = 0;
		start.curB = 0;
		start.opnum = 7;
		print(bfs(start));
		cout << "success" << endl;
	}
}

When I was angry, I found a feature from the silly batch output of my code:

So I wrote the following code of violent cycle:

#include<iostream>
#include<vector>
#include<string>
#include<cstring>

using namespace std;

const string operation[4] = { "success","fill A","empty B","pour A B"};

int limitA, limitB, target;//A B C

int curA, curB;

vector<int>op;

void fillA()
{
	curA = limitA;
}
void emptyB()
{
	curB = 0;
}
void pourAB()
{
	int sub = limitB - curB;
	if (curA > sub)
	{
		curB = limitB;
		curA -= sub;
	}
	else
	{
		curB += curA;
		curA = 0;
	}
}

void Fun()
{
	while (true)
	{
		if (curA != limitA)
		{
			fillA();
			op.push_back(1);
		}
		pourAB();
		op.push_back(3);
		if (curB == target||curA == target)
		{
			op.push_back(0);
			return;
		}
		if (curB == limitB)
		{
			emptyB();
			op.push_back(2);
			pourAB();
			op.push_back(3);
		}
	}
}

void Print()
{
	for (int i = 0; i < op.size(); i++)
	{
		cout << operation[op[i]] << endl;
	}
}

int main()
{
	while (cin >> limitA >> limitB >> target)
	{
		curA = curB = 0;
		op.clear();
		Fun();
		Print();
	}
}

Yes, this violent algorithm it AC!!!
Human deception.
As expected, the exhaustive method is the fundamental way to solve all problems.