迷宫：找到通路

找到通路

1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1

#include<iostream>
#include<cassert>
#include<stack>
using namespace std;
struct pos
{
 int row;
 int col;
};
stack<pos> paths;
void CreateMaze(int* maze,int m,int n)
{
 FILE* fout = fopen("Maze.txt", "r");
 assert(fout);
 for (int i = 0; i < m; ++i)
 {
  for (int j = 0; j < n; ++j)
  {
   char ch = fgetc(fout);
   if (ch == ‘0‘ || ch == ‘1‘)
    maze[i*n + j] = ch - ‘0‘;
   else
    --j;
  }
 }
 fclose(fout);
}
void Display(int *maze, int m, int n)
{
 for (int i = 0; i < m; ++i)
 {
  for (int j = 0; j < n; ++j)
  {
   cout << maze[i*n + j] << " ";
  }
  cout << endl;
 }
 cout << endl;
}
bool CheckAccess(int *maze,int m, int n,pos &  p)
{
 if ((p.row < 0 || p.row >= m || p.col < 0 || p.col >= n) || maze[p.row*n + p.col] != 0)
  return false;
 return true;
}
bool GetPath(int *maze, int m, int n, const pos& entry)
{
 paths.push(entry);
 while (!paths.empty())
 {
  pos cur = paths.top();
  maze[cur.row*n + cur.col] = 2;
  if (cur.row == m - 1)
   return true;
  pos next = cur;
  //上
  next.col -= 1;
  if (CheckAccess(maze, m, n, next))
  {
   paths.push(next);
   continue;
  }
  //下
  next.col += 2;
  if (CheckAccess(maze, m, n, next))
  {
   paths.push(next);
   continue;
  }
  next.col -= 1;
  next.row -= 1;
  if (CheckAccess(maze, m, n, next))
  {
   paths.push(next);
   continue;
  }
  next.row += 2;
  if (CheckAccess(maze, m, n, next))
  {
   paths.push(next);
   continue;
  }
  paths.pop();
 }
 return false;
}
void Test1()
{
 int maze[10][10];
 CreateMaze((int*)maze, 10, 10);
 Display((int*)maze, 10, 10);
 pos p;
 p.row = 1;
 p.col = 0;
 if (GetPath((int*)maze, 10, 10, p))
 {
  while (!paths.empty())
  {
   cout << "(" << paths.top().row << "," << paths.top().col << ")->";
   paths.pop();
  }
 }
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1746339

迷宫：找到通路

原文：http://10541556.blog.51cto.com/10531556/1746339