【问题1】有一个用二维数组表示的迷宫地图，0表示通道，1表示围墙。从迷宫任何位置每次只能向上、向下、向左、向右走一步，每一步长度为1。编写算法，输入起点位置和终点位置，寻找长度最短走出迷宫的路径；如果不存在路径，则显示不存在路径的信息。

#include <iostream>
#include <vector>
#include <stack>
#include<queue>
using namespace std;

typedef struct tagPoint
{
	int x;
	int y;
}Point;

typedef struct tagNode
{
	int x;
	int y; int len;
}Node;
const int INF = 9999;
vector<vector < int >> vAmaze = {
	{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
	{ 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
	{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
	{ 1, 0, 1, 1, 1, 0, 0, 0, 0, 1 },
	{ 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
	{ 1, 0, 1, 0, 0, 0, 1, 0, 0, 1 },
	{ 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
	{ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
	{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};

vector<vector<int >> vLength;
vector<vector<Point >> vPath;
void FindShortestPath(int x1, int y1)
{
	if (vAmaze[x1][y1] == 1)
		return;
	queue<Node> qNode;
	Node e, ex;
	int w = vAmaze[0].size();
	int h = vAmaze.size();
	e.x = x1;
	e.y = y1;
	e.len = 0;
	qNode.push(e);

	while (!qNode.empty()) {
		e = qNode.front();
		qNode.pop();
		vAmaze[e.x][e.y] = 2;

		if (e.x > 0 && vAmaze[e.x - 1][e.y] == 0)
		{
			ex.x = e.x - 1;
			ex.y = e.y;
			ex.len = e.len + 1;
			if (ex.len < vLength[ex.x][ex.y])
			{
				vLength[ex.x][ex.y] = ex.len;
				vPath[ex.x][ex.y].x = e.x;
				vPath[ex.x][ex.y].y = e.y;
			}
			qNode.push(ex);
		}
		if (e.x < h - 1 && vAmaze[e.x + 1][e.y] == 0)
		{
			ex.x = e.x + 1;
			ex.y = e.y;
			ex.len = e.len + 1;
			if (ex.len < vLength[ex.x][ex.y]) {
				vLength[ex.x][ex.y] = ex.len;
				vPath[ex.x][ex.y].x = e.x;
				vPath[ex.x][ex.y].y = e.y;
			}
			qNode.push(ex);
		}
		if (e.y > 0 && vAmaze[e.x][e.y - 1] == 0)
		{
			ex.x = e.x;
			ex.y = e.y - 1;
			ex.len = e.len + 1;
			if (ex.len < vLength[ex.x][ex.y])
			{
				vLength[ex.x][ex.y] = ex.len;
				vPath[ex.x][ex.y].x = e.x;
				vPath[ex.x][ex.y].y = e.y;
			}
			qNode.push(ex);
		}
		if (e.y < w - 1 && vAmaze[e.x][e.y + 1] == 0)
		{
			ex.x = e.x;
			ex.y = e.y + 1;
			ex.len = e.len + 1;
			if (ex.len < vLength[ex.x][ex.y])
			{
				vLength[ex.x][ex.y] = ex.len;
				vPath[ex.x][ex.y].x = e.x;
				vPath[ex.x][ex.y].y = e.y;
			}
			qNode.push(ex);
		}
	}
}
void main(void)
{
	int w = vAmaze[0].size();
	int h = vAmaze.size();
	vector<int> v1;
	vector<Point> vp;
	Point pt = { -1, -1 };
	for (int j = 0; j < w; j++)
	{
		v1.push_back(INF);
		vp.push_back(pt);
	}
	for (int j = 0; j < w; j++)
	{
		v1.push_back(INF);
		vp.push_back(pt);
	}
	for (int i = 0; i < h; i++)
	{
		vPath.push_back(vp);
		vLength.push_back(v1);
	}
	int x1, y1;
	int x2, y2;
	cout << "Please enter the x and y of start point (0=<x, y<=9): ";
	cin >> x1 >> y1;
	cout << "Please enter the x and y of end point (O=<x, y<-9): ";
	cin >> x2 >> y2;
	FindShortestPath(x1, y1);
	if (vLength[x2][y2] >= INF)
	{
		cout << "There is no path!" << endl;
		return;
	}
	cout << "The shortest length is : " << vLength[x2][y2] << " ." << endl;
	stack<Point> sPath;
	int x = x2;
	int y = y2;
	for (int k = 0; k < vLength[x2][y2]; k++)
	{
		Point p = vPath[x][y];
		sPath.push(p);
		x = p.x;
		y = p.y;
	}
	while (!sPath.empty()) {
		Point p = sPath.top();
		sPath.pop();
		cout << "(" << p.x << "," << p.y << ")->";
	}
	cout << "(" << x2 << "," << y2 << ")" << endl;
}

【问题2】据美国动物分类学家欧内斯特-迈尔推算，世界上有超过100万种动物，各种动物有自己的语言 所以，动物A、C之间通信需要动物B来当翻译。问两个动物之间项目通信至少需要多少个翻译。
测试数据中第一行包含两个整数n（2<= n<= 200）、m（1 <= m <= 300），其中n代表动物的数量，动物编号从0开始，n个动物编号为0–n-1，m表示可以相互通信动物数，接下来的m行中包含两个数字分别代表两种动物可以相互通信，在接下来包含一个整数k（k <= 20）,代表查询的数量，每个查找包含两个数字，表示两个动物想要与对方通信。
编写程序，对于每个查询，输出这两个动物彼此通信至少需要多少个翻译，若它们之间无法通过翻译来通信，则输出-1。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef struct tagNode {
	int x;
	int num;
}Node;

typedef struct tagQuestion {
	int a;
	int b;
}Question;

vector<vector<bool>> vTalks;
vector<Question> vQuestions;

int FindLeastTranslator(int a, int b) {
	queue<Node>qNode;
	vector<bool> vVisited;
	Node e, ex;

	for (int j = 0; j < vTalks[0].size(); j++)
		vVisited.push_back(false);
	e.x = a;
	e.num = 0;
	vVisited[e.x] = true;
	qNode.push(e);

	while (!qNode.empty()) {
		e = qNode.front();
		qNode.pop();

		if (e.x == b)
			return e.num - 1;
		for (int j = 0; j < vTalks[e.x].size(); j++) {
			if (j != e.x && vTalks[e.x][j] && !vVisited[j])
			{
				ex.x = j;
				ex.num = e.num + 1;
				vVisited[j] = true;
				qNode.push(ex);
			}
		}
	}
	return -1;
}

void main(void) {
	int n, m;

	cin >> n >> m;
	vector<bool> vt;
	for (int j = 0; j < n; j++)
		vt.push_back(false);

	for (int i = 0; i < n; i++)
		vTalks.push_back(vt);
	for (int k = 0; k < m; k++) {
		int a, b;
		cin >> a >> b;
		vTalks[a][b] = true;
		vTalks[b][a] = true;
	}
	int x;
	cin >> x;
	for (int k = 0; k < x; k++) {
		Question q;
		cin >> q.a >> q.b;
		vQuestions.push_back(q);
	}
	for (int k = 0; k < vQuestions.size(); k++) {
		int a = vQuestions[k].a;
		int b = vQuestions[k].b;
		cout << FindLeastTranslator(a, b) << endl;
	}
}