迷宮走訪 Maze Traversal

題目:
一、隨機產生一個12X12的迷宮(入口在左邊、出口在右邊)，無須確保能從入口走到出口。

二、隨機產生三組能走到出口的迷宮，以x代表走過的路徑。每次輸出兩個迷宮，一個是產生的迷宮，一個是迷宮的走法。(無須是最短路徑)

三、讀一個迷宮檔案進來，並輸出走訪結果，如果走不出去，還要再輸出"This maze has  no solution"。

解題思路:
第一題網路上都說要用到甚麼二元樹，但根本沒教過，反正助教只要求「有出入口、裡面有牆有路」就好，所以我寫的很爛~
第二題則是先生成一條能走到底的路徑，然後在剩下的空間隨機改為路。
第三題因為solution實作一直有點問題，最後是拿這篇去改的。
(因為學期末有拿這題進階出題，變成malloc宣告)

程式碼:
第一題

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int main()
{
 int in = 0, out = 0;
 srand(time(NULL));
 char maze[12][12] ;
 for (int i = 0; i < 12; i++)
 {
  for (int j = 0; j < 12; j++)
   maze[i][j] = '#';
 }
 in = rand() % 11 + 1;
 out = rand() % 11 + 1;
 maze[in][0] = '.';
 maze[out][11] = '.';
 for (int i = 0; i < 100; i++)
 {
  int x, y;
  x = rand() % 10 + 1;
  y = rand() % 10 + 1;
  maze[x][y] = '.';
 }
 for (int i = 0; i < 12; i++)
 {
  for (int j = 0; j < 12; j++)
   printf("%c", maze[i][j]);
  printf("\n");
 }
 return 0;
}

第二題

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define up 0
#define down 1
#define right 2
#define left 3
char find_solution(char maze[12][12], int x, int y,int direction);
int main()
{
 int randomx, randomy;
 int x=0, y=0,direction=0;
 char maze[12][12];
 for (int i = 0; i < 12; i++)//initialze the maze
 {
  for (int j = 0; j < 12; j++)
   maze[i][j] = '#';
 }
 srand(time(NULL));
 int in, out;//set the entrance and exit
 in = rand() % 10 + 1;
 out = rand() % 10 + 1;
 maze[in][0] = '.';
 maze[out][11] = '.';
 x = in;
 maze[x][++y] = '.';
 while (x!=out||y!=11)//make the maze
 {
  direction = rand() % 3;//0~2
  if (direction == up&&(x-1)>=1)
  {
   maze[--x][y] = '.';
  }
  else if (direction == down && (x + 1) != 11)
  {
   maze[++x][y] = '.';
  }
  else if (direction == right&&(y+1)<=10)
  {
   maze[x][++y] = '.';
  }
  else if (direction == right && (y + 1) == 11)
  {
   if (x == out)
    maze[x][++y] = '.';
  }

 }
 for (int i = 0; i < 20; i++)
 {
  randomx = rand() % 10 + 1;
  randomy = rand() % 10 + 1;
  maze[randomx][randomy] = '.';
 }
 x = in;//at the entrance and face right
 y = 0;
 direction = right;
 for (int i = 0; i < 12; i++)
 {
  for (int j = 0; j < 12; j++)
   printf("%c", maze[i][j]);
  printf("\n");
 }
 printf("\n");
 find_solution(maze, x, y,right);
 for (int i = 0; i < 12; i++)
 {
  for (int j = 0; j < 12; j++)
   printf("%c", maze[i][j]);
  printf("\n");
 }
 return 0;
}
char find_solution(char maze[12][12], int x, int y,int direction)
{
 maze[x][y] = 'x';
 if (y >= 11)
  return 'x';
 if (direction = right)
 {
  if (maze[x][y+1]=='#')
  {
   if (maze[x + 1][y] == '.')
    find_solution(maze, x + 1, y, down);
   else
    find_solution(maze, x - 1, y, up);
  }
  else if (maze[x + 1][y] == '.')
   find_solution(maze, x + 1, y, down);
  else
   find_solution(maze, x, y + 1, right);
   
 }
 else if (direction == up)
 {
  if (maze[x][y+1] == '.' || maze[x][y+1] == 'X')
  {
   if (maze[x][y + 1] == '.')
    find_solution(maze, x, y + 1, right);
   else
    find_solution(maze, x, y - 1, left);
  } 
  else
   find_solution(maze, x - 1, y, up);
 }
 else if (direction == down)
 {
  if (maze[x][y-1] == '.' || maze[x][y-1] == 'X')
  {
   if (maze[x][y - 1] == '.')
    find_solution(maze, x, y - 1, left);
   else
    find_solution(maze, x, y + 1, right);
  }
   
  else
   find_solution(maze, x, y + 1, down);
 }
}

第三題

#include "FileHandler.h"
#include<stdio.h>
#include<stdlib.h>
//#define up 0
//#define down 1
//#define left 2
//#define right 3
enum DIR { left, right, up, down };

void mazeTraverse(char **maze, int s_x, int s_y, int g_x, int g_y,int maze_width)
{
 int x, y,check=0;
 enum DIR dir;

 x = s_x, y = s_y;
 if (y == 0)
  dir = right;
 else if (x == 0)
  dir = down;
 else if (y == maze_width-1)
  dir = left;
 else
  dir = up;

 while (1)
 {
  maze[x][y] = 'x';
  if (dir == right)
  {
   if (maze[x + 1][y] != '#')
   {
    x++;
    dir = down;
   }
   else
   {
    if (maze[x][y + 1] == '#')
     dir = up;
    else
     y++;
   }
  }
  else if (dir == left)
  {
   if (maze[x - 1][y] != '#')
   {
    x--;
    dir = up;
   }
   else
   {
    if (maze[x][y - 1] == '#')
     dir = down;
    else
     y--;
   }
  }
  else if (dir == up)
  {
   if (maze[x][y + 1] != '#')
   {
    y++;
    dir = right;
   }
   else
   {
    if (maze[x - 1][y] == '#')
     dir = left;
    else
     x--;
   }
  }
  else if (dir == down)
  {
   if (maze[x][y - 1] != '#')
   {
    y--;
    dir = left;
   }
   else
   {
    if (maze[x + 1][y] == '#')
     dir = right;
    else
     x++;
   }
  }
  if (y < 0)
   break;
  if (check == 0)
  {
   if (x == s_x && y == s_y)
    break;
  }
  if (x == g_x && y == g_y)
  {
   maze[x][y] = 'x';
   break;
  }
  check = 1;
 }
}

int main()
{
 int maze_height , maze_width;//動態配置的部分
 char **maze = NULL;
 char *str = readAllTextFromFile("../maze.txt");
 for (int i = 0;; i++)
 {
  if (str[i] == '\n')
  {
   maze_height = i;
   maze_width = i;
   break;
  }
 }
 maze = (char**)malloc(sizeof(char*)*maze_height);
 for (int i = 0; i < maze_height; i++)
  maze[i] = (char*)malloc(sizeof(char)*maze_width);

 int k = 0, x = 0, y = 0;
 for (int i = 0; i < maze_height; i++)//讀迷宮進來
 {
  for (int j = 0; j < maze_width + 1; j++)
  {
   if (j != maze_width)
    maze[i][j] = str[k++];
   else
    k++;
  }

 }
 int x_out, y_out=11;
 for (int i = 0; i < maze_height; i++)//找入口
 {
  if (maze[i][0] == '.')
   x = i;
  if (maze[i][maze_width - 1] == '.')
   x_out = i;
 }
 mazeTraverse(maze, x, y,x_out,y_out ,maze_width);
 for (int i = 0; i < maze_height; i++)//結果
 {
  for (int j = 0; j < maze_width; j++)
   printf("%c", maze[i][j]);
  printf("\n");
 }
 for (int i = 0; i < maze_height; i++)
 {
  if (maze[i][maze_width - 1] == '.')
   printf("this maze has no solution.\n");
 }
 return 0;
}