算法之深度优先寻路

.cpp文件

#include<iostream>
#include"myPoint.h"
using std::cin;
using std::cout;
using std::endl;
#define N 10
#define M 10

enum myDir { p_up,p_left, p_down,  p_right };

struct myPoint
{
	int row, col;
};

struct myNode_val
{
	int value;
	bool isFind;
	myDir dir;

};
bool isMove(myNode_val Point[][M], int row, int col)
{
	if (row < 0 || row >= N || col < 0 || col >= M)
	{
		return false;
	}
	if (Point[row][col].isFind != false || Point[row][col].value != 0)
	{
		return false;
	}
	return true;
}
int main()
{
	int pathMap[N][M] = {
		{1,1,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,0,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1},
	};

	myNode_val myNode[N][M];
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			myNode[i][j].value = pathMap[i][j];
			myNode[i][j].isFind = false;
			myNode[i][j].dir = p_up;
		}
	}
	myPoint beginPoint = { 1,1 };
	myPoint endPoint = { 8,8 };
	myNode_in_out<myPoint> node;
	node.push(beginPoint);
	myPoint nearPoint = beginPoint;
	while (true)
	{
		switch (myNode[nearPoint.row][nearPoint.col].dir)
		{
		case p_up:
			myNode[nearPoint.row][nearPoint.col].dir = p_left;
			if (isMove(myNode, nearPoint.row - 1, nearPoint.col))
			{
				myNode[nearPoint.row][nearPoint.col].isFind = true;
				myPoint tempPoint = { nearPoint.row - 1,nearPoint.col };
				node.push(tempPoint);
				nearPoint = tempPoint;
			}
			break;
		case p_left:
			myNode[nearPoint.row][nearPoint.col].dir = p_down;
			if (isMove(myNode, nearPoint.row, nearPoint.col - 1))
			{
				myNode[nearPoint.row][nearPoint.col].isFind = true;
				myPoint tempPoint = { nearPoint.row ,nearPoint.col - 1 };
				node.push(tempPoint);
				nearPoint = tempPoint;
			}
			break;
		case p_down:
			myNode[nearPoint.row][nearPoint.col].dir = p_right;
			if (isMove(myNode, nearPoint.row + 1, nearPoint.col))
			{
				myNode[nearPoint.row][nearPoint.col].isFind = true;
				myPoint tempPoint = { nearPoint.row + 1,nearPoint.col };
				node.push(tempPoint);
				nearPoint = tempPoint;
			}
			break;
		case p_right:
			if (isMove(myNode, nearPoint.row, nearPoint.col + 1))
			{
				myNode[nearPoint.row][nearPoint.col].isFind = true;
				myPoint tempPoint = { nearPoint.row ,nearPoint.col + 1 };
				node.push(tempPoint);
				nearPoint = tempPoint;
			}
			else
			{
				myPoint tempPoint = node.getTop();
				myNode[tempPoint.row][tempPoint.col].isFind = true;
				node.pop();
				if (!node.empty())
				{
					nearPoint = node.getTop();
				}
			}
			break;
		}
		if (nearPoint.row == endPoint.row && nearPoint.col == endPoint.col)
		{
			break;
		}
		if (node.empty())
		{
			break;
		}
	}
	while (!node.empty())
	{
		myPoint tempPoint = node.getTop();
		cout << tempPoint.row << " " << tempPoint.col << endl;
		node.pop();
	}
	cin.get();
	return 0;
}

.h文件（myPoint.h）

#pragma once

template<class T>
class myNode_in_out
{
private:
	T* p;
	size_t len;
	size_t max_size;
public:
	myNode_in_out();
	~myNode_in_out();
	void clear();
	void push(T const& elem);
	void pop();
	T getTop();
	bool empty();
};

template<class T>
myNode_in_out<T>::myNode_in_out()
{
	p = nullptr;
	len = max_size = 0;
}

template<class T>
inline myNode_in_out<T>::~myNode_in_out()
{
	clear();
}

template<class T>
void myNode_in_out<T>::clear()
{
	if (p)
	{
		delete[] p;
		len = max_size = 0;
	}
	p = nullptr;
}

template<class T>
void myNode_in_out<T>::push(T const&elem)
{
	if (len >= max_size)
	{
		max_size = max_size + ((max_size >> 1) > 1 ? (max_size >> 1) : 1);
		T *temp = new T[max_size];
		for (size_t i = 0; i < len; ++i)
		{
			temp[i] = p[i];
		}
		if (p)
		{
			delete[] p;
		}
		p = temp;
	}
	p[len++] = elem;
}

template<class T>
void myNode_in_out<T>::pop()
{
	--len;
}

template<class T>
T myNode_in_out<T>::getTop()
{
	return p[len - 1];
}

template<class T>
bool myNode_in_out<T>::empty()
{
	return len == 0;
}