main.cpp

来自「我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:」· C++ 代码 · 共 125 行

/***********************************************************************************
12. 下图是一个集装箱仓库，阴影部分表示有集装箱存放不能通过，无阴影处为临时通
 道。当有人要从入口处到达出口处时，必须寻找可通过路线，请你找出可完成这个过程
 的最方便（即用最短路线）到达出口处的路径。

          ┎┰┰┰入口┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┒
          ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂╂┸┸╂╂╂┨
          ┠╂╂╂──╂┸┸╂──╂┰┰╂┰┰╂──╂╂╂╂──╂╂╂┨
          ┠╂╂╂──╂┰┰╂┰┰╂╂╂╂╂╂╂──╂┸┸╂──╂╂╂┨
          ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂┨
          ┠╂╂╂──╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂┨
          ┠╂╂╂──╂┰┰╂┰┰╂┰┰╂──╂┰┰╂──╂┰┰╂╂╂┨
          ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂──╂╂╂╂──╂╂╂╂╂╂┨
          ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂──╂╂╂╂──╂┸┸╂╂╂┨
          ┠╂╂╂──╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂╂┰┰╂──╂╂╂┨
          ┖┸┸┸──┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸出口┸┸┸┚
		   输入:入口:(1,2) 出口:(10,9)
		   输出:路径
		   方法: 深度优先,广度优先
************************************************************************************/


//#include <stdio.h>
#include <queue>
using namespace std;

#define ENDDIRT 5

struct Node
{
	int row;
	int col;
};

int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

int maze[10][10] = {
	1,0,1,1,1,1,1,1,1,1,
	1,0,1,0,0,0,0,1,0,1,
	1,0,0,0,1,1,0,1,0,1,
	1,0,1,1,1,1,0,0,0,1,
	1,0,1,1,1,1,1,1,1,1,
	1,0,0,0,0,0,0,0,0,1,
	1,0,1,1,1,0,1,0,1,1,
	1,0,1,1,1,0,1,0,1,1,
	1,0,1,0,0,0,1,0,0,1,
	1,0,1,1,1,1,1,1,0,1}; 

static int dirt[12][12];

void PrintPath(Node start)
{
	int direct;
	Node cur = start;
	printf("(%d,%d)",cur.row,cur.col);
	while((direct=dirt[cur.row][cur.col]) != ENDDIRT)
	{
		cur.row = cur.row - dr[direct];
		cur.col = cur.col - dc[direct];
		printf(" -> (%d,%d)",cur.row,cur.col);
	}
	printf("\n");
}

void main()
{
	int row,col;
	int map[12][12];
	Node cur;
	queue<Node> q;
	Node start = {1,2};
	Node end = {10,9};
	int flag = 0;

	for(row=0; row<12; row++)
	{
		for(col=0; col<12; col++)
			if(row==0 || col==0 || row==11 || col==11)
				map[row][col] = 1;
			else map[row][col] = maze[row-1][col-1];
	}
	q.push(end);
	dirt[end.row][end.col] = ENDDIRT;
	
	while(!q.empty())
	{
		cur = q.front();
		//走过的路要屏蔽掉
		map[cur.row][cur.col] = 1;
		q.pop();
		if(cur.row == start.row && cur.col == start.col)
		{
			flag = 1;
			break;
		}
		else
		{
			int i;
			Node temp;
			for(i=0; i<4; i++)
			{
				temp.row = cur.row + dr[i];
				temp.col = cur.col + dc[i];
				if(map[temp.row][temp.col] == 0)
				{
					q.push(temp);
					dirt[temp.row][temp.col] = i;
				}
			}
		}
	}
	if(flag == 1)
	{
		//输出路径
		printf("Have path!\n");
		PrintPath(start);
	}else
	{
		printf("No path!\n");
	}
	
}