12_3_2.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include "Stack.h"

Point GetPoint(int x, int y, int direction)
{
	switch (direction)
	{
		case 0:
			x--;
			y--;
			break;
		case 1:
			y--;
			break;
		case 2:
			x++;
			y--;
			break;
		case 3:
			x--;
			break;
		case 4:
			x++;
			break;
		case 5:
			x--;
			y++;
			break;
		case 6:
			y++;
			break;
		case 7:
			x++;
			y++;
			break;
		default:
			throw "方向值错误";
	}
	Point p;
	p.x = x;
	p.y = y;
	return p;
}

void main()
{
	bool maze[][10] = {
		{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
		{1, 0, 1, 1, 1, 0, 1, 1, 1, 1},
		{1, 1, 0, 1, 0, 1, 1, 1, 1, 1},
		{1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
		{1, 0, 1, 1, 1, 0, 1, 1, 1, 1},
		{1, 1, 0, 0, 1, 1, 0, 0, 0, 1},
		{1, 0, 1, 1, 0, 0, 1, 1, 0, 1},
		{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
	};

	bool visited[][10] = {
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
	};

	Stack s;
	Point start;
	start.x = 1;
	start.y = 1;
	s.Push(start);
	visited[1][1] = 1;
	bool found = true;
	int x = 1;
	int y = 1;
	cout << "走过的路径：" << endl;
	while (x != 6 || y != 8)
	{
		Point p;
		if (!found)
		{
			p = s.Pop();
			x = p.x;
			y = p.y;
			cout << x << ',' << y << endl;
		}
		found = false;
		for (int d = 0 ;d <= 7; d++)
		{
			Point p2 = GetPoint(x, y, d);
			if (maze[p2.x][p2.y] == 0 && !visited[p2.x][p2.y])
			{
				s.Push(p2);
				visited[p2.x][p2.y] = 1;
				x = p2.x;
				y = p2.y;
				cout << x << ',' << y << endl;
				found = true;
				break;
			}
		}
	}
	cout << endl << "正确的路径: " << endl;
	s.PrintRightPath();
}