使用 Dfs 算法达到目标

Question

#include <stdio.h>

char matrix[8][8];

struct coordinate {
  int a;
  int b;
};

void ReadFile() {
  printf("\n\n\n                START MAZE  ");
  int x, y;
  FILE * file1;
  file1 = fopen("NEWmaze.txt", "r");

  for (x = 0; x < 8; x++) {
    for (y = 0; y < 8; y++) {
      fscanf(file1, " %c", & matrix[x][y]);

    }
    printf("\n");
  }
}

void PrintMaze() {
  int x, y;
  for (x = 0; x < 8; x++) {
    printf("                ");
    for (y = 0; y < 8; y++) {

      printf(" %c ", matrix[x][y]);
    }

    printf("\n");
  }
  printf("\n\n\n\n");
}

struct coordinate DFS(int x, int y) {

  struct coordinate retval = {
    x,
    y
  };

  printf("%c", matrix[x - 1][y]); //saw the target but could not stop

  if (matrix[x][y - 1] == '-') //WEST
  {
    printf("WEST");
    //      printf("%d %d",x,y-1); step by step

    matrix[x][y - 1] = '.';
    PrintMaze(); //step by step
    DFS(x, y - 1);
    struct coordinate retval = {
      x,
      y - 1
    };

  }
  if (matrix[x][y - 2] == 'g' && matrix[x + 1][y - 2] != '#') {

    //  printf("%d %d ",x,y-2); step by step

    return retval;
  }

  if (matrix[x - 1][y] == '-') //NORTH
  {

    //    printf("%d %d",x-1,y); step by step
    matrix[x - 1][y] = '.';
    PrintMaze(); //step by step
    DFS(x - 1, y);
    struct coordinate retval = {
      x - 1,
      y
    };

  }
  if (matrix[x - 2][y] == 'g' && matrix[x - 3][y] != '#') {
    struct coordinate retval = {
      0,
      0
    };

    return retval;
  }

  if (matrix[x][y + 1] == '-') //SOUTH
  {
    //printf("%d %d",x,y+1); step by step
    matrix[x][y + 1] = '.';
    PrintMaze();
    DFS(x, y + 1);
    struct coordinate retval = {
      x,
      y + 1
    };
  }
  if (matrix[x + 1][y + 1] == 'g' && matrix[x + 2][y + 1] != '#') {
    struct coordinate retval = {
      0,
      0
    };

    return retval;
  }

  if (matrix[x + 1][y] == '-') { // EAST

    // printf("%d %d",x+1,y);

    matrix[x + 1][y] = '.';
    //PrintMaze();
    DFS(x + 1, y);
    struct coordinate retval = {
      x + 1,
      y
    };

  }
  if (matrix[x + 1][y + 1] == 'g' && matrix[x + 1][y + 2] != '#') {
    struct coordinate retval = {
      0,
      0
    };

    return retval;
  }

  return retval;
}

void StartSearch() {
  printf("                  STEP BY STEP");

  int x, y;

  for (x = 0; x < 8; x++) {
    for (y = 0; y < 8; y++) {
      if (matrix[x][y] == 's') //START
      {

        struct coordinate coord = DFS(x, y);

      }
    }

    printf("\n");

  }

}

int main() {
  ReadFile();

  PrintMaze();
  StartSearch();

  PrintMaze();

  return 0;
}

newMaze.txt 文件（# wall, . step, - empty , s start,g goal）

# # # # # # # #  
# g - - # - - #       
# - - - - - # # 
# - - # - - - # 
# - - # - - # #
# - - - - - - # 
# - # - - - s #
# # # # # # # #

我打印了步骤，我可以看到它达到了 goal.The 唯一的问题是当我达到目标时它不会停止（'g'）。当我使用 while break 时它不能'不要跳出无限循环。如何让它在到达目标('g')时停止？

这是 ->

的跟进

( here i tried using struct as x and y are not returning at the same time )

更新

 #include <stdio.h>
    
    char matrix[8][8];
    
    struct coordinate {
        int x, y;
    };
    
    void ReadFile()
    {
        printf("\n\n\n                START MAZE  ");
        int x,y;
        FILE *file1;
        file1=fopen("NEWmaze.txt","r");
     
        for(x=0; x<8; x++){
            for(y=0;y<8;y++)
            {
            fscanf (file1, " %c", &matrix[x][y]);
            
          
           }
        printf("\n");
        }
    }
    
    
      
    void PrintMaze()
    { 
        int x,y;
        for(x=0;x<8;x++)
        {
            printf("                ");
            for(y=0;y<8;y++)
            {
                 
                printf(" %c ",matrix[x][y]);
            }
         
        printf("\n");       
        }
        printf("\n\n\n\n");
    }
      
    struct coordinate DFS(int x, int y)
    {
        struct coordinate retval = { -1, -1 };
        if (matrix[x][y] == 'g')
        {
            retval.x = x;
            retval.y = y;
        }
        else if (matrix[x][y] == '-' )
        {
            matrix[x][y] = 'o';// West North South East
            PrintMaze();
            retval = DFS(x, y-1); if (retval.x != -1) return retval;
            retval = DFS(x-1, y ); if (retval.x != -1) return retval;
            retval = DFS(x , y+1); if (retval.x != -1) return retval;
            retval = DFS(x + 1, y); matrix[x][y] = '.';
        }
        return retval;
    }
        
    void StartSearch()
    { 
        printf("                  STEP BY STEP");
    
        int x,y;
    
        for(x=0;x<8;x++)
        {
            for(y=0;y<8;y++)
            {
                if(matrix[x][y] == 's')//START  
                {
                    if(matrix[x][y-1] == '-')
                    {
                         DFS(x,y-1);
                    }
                        if(matrix[x-1][y] == '-')
                    {
                         DFS(x-1,y);
                    }
                        if(matrix[x][y+1] == '-')
                    {
                         DFS(x,y+1);
                    }
                        if(matrix[x+1][y] == '-')
                    {
                         DFS(x+1,y);
                    }
                  
                
    
    
                  
     
                 }
            }
    
            
        printf("\n");  
             
        }
     
    }
     
    int main()
    {
        ReadFile();
        
        PrintMaze();
        StartSearch();
        
         
        PrintMaze();
        
        return 0;
    }

更新输出

我按优先顺序写的，它有效。

Answer 1

您正在以一种奇怪的方式处理 return 值。与其在递归调用之后构造它，不如简单地使有效的 co-ordinate 被 returned 如果当前位置是目标。否则，return 一些无效的东西（例如 {-1,-1}，或者在你的情况下甚至是 {0,0} 如果那总是一堵墙）。

现在您需要做的就是存储每个递归调用的 return 值并检查它是否有效。如果是，则立即return。否则继续处理（即测试其他方向）。

就代码而言，是这样的：

struct coordinate {
    int x, y;
};

struct coordinate DFS(int x, int y)
{
    struct coordinate retval = { -1, -1 };
    if (matrix[x][y] == 'g')
    {
        retval.x = x;
        retval.y = y;
    }
    else if (matrix[x][y] == '-' || matrix[x][y] == 's')
    {
        matrix[x][y] = '.';
        retval = DFS(x - 1, y); if (retval.x != -1) return retval;
        retval = DFS(x, y - 1); if (retval.x != -1) return retval;
        retval = DFS(x + 1, y); if (retval.x != -1) return retval;
        retval = DFS(x, y + 1);
    }
    return retval;
}

如果您的迷宫的周边始终有一堵墙，则您无需在 co-ordinate 上执行任何 bounds-testing，因为在边缘时您永远不会执行递归。

您甚至可以稍微重新排序以绘制您第一次到达目标时使用的实际路径。它可能不是最佳路径，但这需要更高级的算法。下面，我们使用 'o' 来表示通往目标路径上的一个单元格。

struct coordinate DFS(int x, int y)
{
    struct coordinate retval = { -1, -1 };
    if (matrix[x][y] == 'g')
    {
        retval.x = x;
        retval.y = y;
    }
    else if (matrix[x][y] == '-' || matrix[x][y] == 's')
    {
        matrix[x][y] = '.';
        retval = DFS(x - 1, y);
        if (retval.x == -1) retval = DFS(x, y - 1);
        if (retval.x == -1) retval = DFS(x + 1, y);
        if (retval.x == -1) retval = DFS(x, y + 1);
        if (retval.x != -1) matrix[x][y] = 'o';
    }
    return retval;
}

并对搜索功能稍作调整：

void StartSearch()
{
    int x, y;
    for (x = 0; x < 8; x++) {
       for (y = 0; y < 8; y++) {
            if (matrix[x][y] == 's')
            {
                DFS(x, y);
                matrix[x][y] = 's';
            }
        }
    }
}

你得到这个输出：

                 #  #  #  #  #  #  #  # 
                 #  g  o  o  #  .  .  # 
                 #  -  -  o  o  o  #  # 
                 #  -  -  #  -  o  -  # 
                 #  -  -  #  -  o  #  # 
                 #  -  -  -  -  o  o  # 
                 #  -  #  -  -  -  s  # 
                 #  #  #  #  #  #  #  #