Week2作业：BFS迷宫与倒水问题
A-Maze
题目内容
东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。既然已经知道了地图，那么东东找到妹纸就不难了，请你编一个程序，写出东东找到妹纸的最短路线。
输入格式
输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。
输出格式
输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。
样例
输入
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
输出
(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)
备注
坐标(x, y)表示第x行第y列，行、列的编号从0开始，且以左上角为原点。
另外注意，输出中分隔坐标的逗号后面应当有一个空格。
解题思路
经典的迷宫题，乍一眼把Maze真的当成了“妹纸” ，思路就是bfs，在遍历到某个点时时刻记录这个点的父亲点，以用作最后输出使用。
话不多说，直接上代码：
#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为下一步 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;//先进后出输出路径~
}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-倒水问题
题目内容
倒水问题 “fill A” 表示倒满A杯，"empty A"表示倒空A杯，“pour A B” 表示把A的水倒到B杯并且把B杯倒满或A倒空。
真的就是那个3 5杯子倒4水的经典问题，只不过这次要求任意一对杯子。
输入格式
输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 且A和B互质(必要条件)
输出格式
你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始，不应该有空行或任何尾随空格。
样例
2 7 5
2 7 4
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success
备注
如果你的输出与Sample Output不同，那没关系。对于某个"A B C"本题的答案是多解的，不能通过标准的文本对比来判定你程序的正确与否。
解题思路
其实稍微想一想就会发现，面临每一次操作的时候，我们都有六种选择：
- 把A倒满
- 把B倒满
- 把A倒空
- 把B倒空
- 把A中的水倒进B
- 把B中的水倒进A
这样子我们只需要bfs遍历每一层选择就行了。
一个可行的剪枝：
- A空的时候无法倒空也无法倒进B
- A满的时候无法倒满也无法从B倒A
- 以上AB互换同理
以下是本人的代码，能正确输出却WA，心塞：
#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;}
}
在恼怒的时候，我从自己代码的憨批输出中发现了一个特点：
它特别喜欢重复以下操作：
1.把较大的倒满
2.把大的倒进小的
3.把小的倒空
如此循环。
在任何时候当较大的那个空了之后就暂停循环，倒满它，然后继续循环…(一台无情的复读机)
由于A B互质 所以这样子复读一定能够达到结果(就是可能答案会比较蠢，不过答案肯定是对的嘛！)
于是我写出了如下的暴力循环代码：
#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 Cint 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();}
}
是的，这个暴力算法它AC了！！！
人类迷惑行为。
果然穷举法是解决一切问题的根本方法。
发布评论