迷宮最短路徑問題

(文章目錄)

一.迷宮最短路徑問題

小青蛙有一天不小心落入了一個地下迷宮,小青蛙希望用自己僅剩的體力值P跳出這個地下迷宮。為了讓問題簡單,假設這是一個n*m的格子迷宮,迷宮每個位置為0或者1,0代表這個位置有障礙物,小青蛙達到不了這個位置;1代表小青蛙可以達到的位置。小青蛙初始在(0,0)位置,地下迷宮的出口在(0,m-1)(保證這兩個位置都是1,并且保證一定有起點到終點可達的路徑),小青蛙在迷宮中水準移動一個機關距離需要消耗1點體力值,向上爬一個機關距離需要消耗3個機關的體力值,向下移動不消耗體力值,當小青蛙的體力值等于0的時候還沒有到達出口,小青蛙将無法逃離迷宮。現在需要你幫助小青蛙計算出能否用僅剩的體力值跳出迷宮(即達到(0,m-1)位置)。

輸入描述：

輸入包括n+1行:

第一行為三個整數n,m(3 <= m,n <= 10),P(1 <= P <= 100)

接下來的n行:

每行m個0或者1,以空格分隔

輸出描述：

如果能逃離迷宮,則輸出一行體力消耗最小的路徑,輸出格式見樣例所示;如果不能逃離迷宮,則輸出"Can not escape!"。 測試資料保證答案唯一

示例1

輸入：

4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1

複制

輸出：

[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

原題來自于：來自于牛客網的地下迷宮

這道題跟正常迷宮問題大體相似，隻不過引入了體力值的消耗問題

相比較上次的正常迷宮問題，這次的1是通路 ，0是牆壁

1. 整體過程

這裡前面的過程就不說了，需要的可以看：迷宮正常問題

主要從找到通路後，回溯後走到另一條路開始

1.此時走到下标(0,3)時找到出口，回溯時發現隻有達到下标(2,2)時 ，右方向可以走，

2.因為我們遵循 上下左右 四個方向依次遞歸，是以是當下标(2,2)完成了下的遞歸 回溯後，隻有左右兩個方向可以走

當此次完成後的路徑path與minpath最短路徑比較，發現此時為最短路徑。

1.minpath與path之間不能直接拷貝(淺拷貝問題)

path 作為目前路徑，minpath作為最短路徑，當path值小于minpath值時，需要把path值指派給minpath，但是如果我們此時單純指派處理的話會出現問題

1.把path指派給minpath，此時的minpath原來的空間就丢了，造成記憶體洩漏

2.此時的指派是将minpath指向path的空間，因為兩者都需要記憶體銷毀，就會導緻記憶體銷毀兩次

是以為了防止這種情況的發生

将minpath原有的空間銷毀掉，再動态開辟一塊跟path相同大小的空間，并将path的值拷貝過來

void stackcopy(ST* minpath, ST* path)
{
		minpath->a = (datatype*)malloc(sizeof(datatype*) * path->capacity);//動态開辟一塊與path一樣大的空間
		memcpy(minpath->a, path->a, sizeof(datatype) * path->top);//使用記憶體拷貝函數将path的内容拷貝過來
		minpath->top = path->top;
		minpath->capacity = path->capacity;
}
           

2.找到一次通路後，如何處置已經變為2的路徑

3. getmazepath不需要判斷是否為真

ST path;
ST minpath;
void stackcopy(ST* minpath, ST* path)
{
		minpath->a = (datatype*)malloc(sizeof(datatype*) * path->capacity);
		memcpy(minpath->a, path->a, sizeof(datatype) * path->top);
		minpath->top = path->top;
		minpath->capacity = path->capacity;
}
void  getmazepath(int** maze, int N, int M, PT cur,int p)
{
	stackpush(&path, cur);//入棧
	if (cur.row == 0 && cur.col == M - 1)//出口
	{
		//找到最短路徑，更新minpath 要保證體力>=0
		if (p >= 0 && stackempty(&minpath) || stacksize(&path) < stacksize(&minpath))
		{
			stackdestroy(&minpath);
			stackcopy(&minpath, &path);//将path賦給minpath
		}
	}
	maze[cur.row][cur.col] = 2;//先将目前所處位置指派為2 
	PT next;

	next = cur;//上
	next.row -= 1;
	if (ispass(maze, N, M, next))//判斷上的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p-3);
	}

	next = cur;//下
	next.row += 1;
	if (ispass(maze, N, M, next))//判斷下的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p);
		
	}

	next = cur;//左
	next.col -= 1;
	if (ispass(maze, N, M, next))//判斷左的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p-1);
	}

	next = cur;//右
	next.col += 1;
	if (ispass(maze, N, M, next))//判斷右的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p-1);
	}
	maze[cur.row][cur.col] = 1;//恢複公共路徑
	stackpop(&path);   //如果上下左右都不滿足就移除棧頂元素
}
           

4.整體代碼

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
typedef struct postion
{
	int row;//行
	int col;//列
}PT;
/////////////////////////////////////////
typedef PT datatype;//将資料類型改為結構體
typedef struct stack
{
	datatype* a;
	int top;
	int capacity;
}ST;
void stackinit(ST* p);
void stackpush(ST* p, datatype x);
datatype stacktop(ST* p);
void stackpop(ST* p);
int stacksize(ST* p);
bool stackempty(ST* p);
void stackdestroy(ST* p);
////////////////////////////////////////
void stackinit(ST* p)//棧的初始化
{
	assert(p);
	p->a = NULL;
	p->top = 0;
	p->capacity = 0;
}
void stackpush(ST* p, datatype x)//入棧
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
		datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype) * newcapacity);
		if (tmp != NULL)
		{
			p->a = tmp;
			p->capacity = newcapacity;
		}
	}
	p->a[p->top] = x;
	p->top++;
}
void stackpop(ST* p)//移除棧頂元素
{
	assert(p);
	assert(p->top > 0);
	p->top--;
}
datatype  stacktop(ST* p)//出棧
{
	assert(p);
	assert(p->top > 0);
	return p->a[p->top - 1];
}
bool  stackempty(ST* p)//是否為空
{
	return p->top == 0;
}
int stacksize(ST* p)//棧中元素個數
{
	assert(p);
	return p->top;
}
void stackdestroy(ST* p)//記憶體銷毀
{
	assert(p);
	free(p->a);
	p->a = NULL;
	p->top = 0;
	p->capacity = 0;
}

/// ///////////////////////////////////////


bool ispass(int** maze, int N, int M, PT pos)//現在為1為通道，0為牆壁
{
	if (pos.row >= 0 && pos.row < N && pos.col >= 0 && pos.col < M && maze[pos.row][pos.col] == 1)
	{   //坐标不越界并且該處位置==1
		return true;
	}
	else
	{
		return false;
	}
}
ST path;
ST minpath;
void stackcopy(ST* minpath, ST* path)
{
		minpath->a = (datatype*)malloc(sizeof(datatype*) * path->capacity);
		memcpy(minpath->a, path->a, sizeof(datatype) * path->top);
		minpath->top = path->top;
		minpath->capacity = path->capacity;
}
void  getmazepath(int** maze, int N, int M, PT cur,int p)
{
	stackpush(&path, cur);//入棧
	if (cur.row == 0 && cur.col == M - 1)//出口
	{
		//找到最短路徑，更新minpath 要保證體力>=0
		if (p >= 0 && stackempty(&minpath) || stacksize(&path) < stacksize(&minpath))
		{
			stackdestroy(&minpath);
			stackcopy(&minpath, &path);//将path賦給minpath
		}
	}
	maze[cur.row][cur.col] = 2;//先将目前所處位置指派為2 
	PT next;

	next = cur;//上
	next.row -= 1;
	if (ispass(maze, N, M, next))//判斷上的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p-3);
	}

	next = cur;//下
	next.row += 1;
	if (ispass(maze, N, M, next))//判斷下的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p);
		
	}

	next = cur;//左
	next.col -= 1;
	if (ispass(maze, N, M, next))//判斷左的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p-1);
	}

	next = cur;//右
	next.col += 1;
	if (ispass(maze, N, M, next))//判斷右的位置是否滿足繼續的條件
	{
		getmazepath(maze, N, M, next,p-1);
	}
	maze[cur.row][cur.col] = 1;//恢複公共路徑
	stackpop(&path);   //如果上下左右都不滿足就移除棧頂元素
}
void printpath(ST* ps)//由于此時的path棧要列印出來會倒着出，
//是以又重新建立了一個棧，将資料導進去
{
	ST rpath;
	stackinit(&rpath);
	while (!stackempty(ps))
	{
		stackpush(&rpath, stacktop(ps));
		stackpop(ps);
	}
	while (stacksize(&rpath)>1)
	{
		PT top = stacktop(&rpath);//此時資料類型被改為PT
		printf("[%d,%d],", top.row, top.col);
		stackpop(&rpath);
	}
	PT top = stacktop(&rpath);//此時資料類型被改為PT
	printf("[%d,%d]", top.row, top.col);
	stackpop(&rpath);
	stackdestroy(&rpath);//記憶體銷毀
}
int main()
{
	int N = 0;
	int M = 0;
	int p = 0;
	while (scanf("%d%d%d", &N, &M,&p) != EOF)//多組輸入
	{
		//動态開辟二維數組
		//1.開辟N個指針數組
		int** maze = (int**)malloc(sizeof(int*) * N);
		//2.開辟M個空間
		int i = 0;
		for (i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int) * M);
		}

		int j = 0;
		for (i = 0; i < N; i++)
		{
			for (j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}
		PT  entry = { 0,0 };
	
		stackinit(&path);
		stackinit(&minpath);
		getmazepath(maze, N, M, entry, p);
		if (!stackempty(&minpath))//如果最短路徑因為體力問題為0 
		{
			printpath(&minpath);
		}
		else
		{
			printf("Can not escape!");
		}

		stackdestroy(&path);
		stackdestroy(&minpath);

		//釋放空間
		//1.釋放N個數組指針指向的空間
		for (i = 0; i < N; i++)
		{
			free(maze[i]);
		}
		//2.将N個指針數組整體釋放
		free(maze);
		maze = NULL;
	}

	return 0;
}