Rat in a maze
#include "stdio.h"
#include "string.h"
#include <iostream>
#define GRAPH_SIZE 10
#define ACT 4
const int dx[ACT] = {1, 0, -1, 0};
const int dy[ACT] = {0, 1, 0, -1};
struct point
{
int x;
int y;
};
int maze[GRAPH_SIZE][GRAPH_SIZE] = { {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1, 0, 0, 0, 0, 0, 0, 0, 0,-1},
{-1, 0, 0,-1, 0, 0, 0, 0, 0,-1},
{-1, 0,-1,-1, 0, 0, 0, 0, 0,-1},
{-1,-1,-1, 0, 0, 0, 0, 0, 0,-1},
{-1, 0, 0, 0, 0, -1, 0, 0, 0,-1},
{-1, 0, 0, 0, 0, -1, 0, 0, 0,-1},
{-1, 0, 0, 0, 0, -1, 0, 0, 0,-1},
{-1, 0, 0, 0, 0, -1, 0, 0, 0,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}};
int DFS(int x, int y, int target_x, int target_y, int d)
{
if ( !(maze[x][y] == -1 || maze[x][y] > 0) ) {
maze[x][y] = d;
if ( !(x == target_x && y == target_y) ) {
for (int i=0; i<ACT; ++i)
{
DFS(x + dx[i], y + dy[i], target_x, target_y, d + 1);
if (maze[target_x][target_y] != 0)
break;
}
if(i == ACT)
maze[x][y] = 0;
}
}
return maze[target_x][target_y];
}
int main(int argc, char* argv[])
{
int ans = 0;
struct point start ={1,1};
struct point end ={8,8};
ans = DFS(start.x, start.y, end.x, end.y,1);
if (ans < 1)
std::cout << "老鼠找不到出口。\n" << !2 <<std::endl;
else
std::cout << "老鼠找到一條路徑,行走距離是:" << ans << std::endl;
for(int i=0; i<GRAPH_SIZE; i++) {
for(int j=0; j<GRAPH_SIZE; j++) {
if(maze[i][j] == -1)
printf("█");
else if(maze[i][j] == 0)
printf(" ");
else
printf("%2d",maze[i][j]);
}
std::cout << std::endl ;
}
return 0;
}