如何在这个扫雷程序中实现递归？ [英] How to implement recursion in this minesweeper program?

问题描述

我的任务是在 C 的模拟​​扫雷游戏中实现递归。它基本上应该自己清除相邻的单元格，只要它可以这样做。我很感激任何帮助指出我的算法中的错误。请记住，我只学习了6周的编程，所以我可能不理解高级解释。谢谢！



（PS：我想发帖实际问题，但似乎这里不可能这样做）



我尝试了什么：

I have a task of implementing recursion in a simulated minesweeper game in C. It should basically call itself to clear neighboring cells, provided it is possible to do so. I would appreciate any help in pointing out the error in my algorithm. And please bear in mind that I have only learnt programming for 6 weeks so I may not understand advanced explanations. Thank you!

(PS: I would like to post the actual question but it seems like it is not possible to do so here)

What I have tried:

#include <stdio.h>
#include <stdbool.h>
#define ROW 16 //max number of rows 
#define COL 30 //max number of columns

void readBoard(int board[][COL], int m, int n);
void printBoard(int board[][COL], int m, int n);
int countNeighbour(int board[][COL], int r, int c, int m, int n);
bool isValid(int r, int c, int m, int n);
bool allCleared(int board[][COL], int m, int n);
void clearNeighbours(int board[][COL], int r, int c, int m, int n); 

int main(void) {
   int r, c, m, n, board[ROW][COL]={{0}}; //initializes all values to 0

   scanf("%d%d", &m, &n);
   readBoard(board, m, n); // reads the board.
   do {
      scanf("%d%d", &r, &c);     
      if(board[r][c] < 9  && isValid(r,c,m,n) == true) { // checks for mines presence and location validity
         if(countNeighbour(board, r, c, m, n) == 0) {
            clearNeighbours(board, r, c, m, n);
         }
      } else break; // escape the loop if the conditions are not fulfilled
   } while (allCleared(board,m,n) == false); // checks if all safe locations are cleared

   printBoard(board, m, n);
   return 0;
}

/* 
  allCleared checks the board and returns true if all safe locations
  have been cleared, false otherwise.
*/
bool allCleared(int board[][COL], int m, int n) {
   int i,j;
   for(i=0; i<m; i++) {
      for(j=0; j<n; j++) {
         if(board[i][j] == -1) {
            return false;
         }
      }
   }
   return true;
}

/* 
  isValid checks if the input location is valid or not.
*/
bool isValid(int r, int c, int m, int n) {
   if(r>=0 && r<=m && c>=0 && c<=n) {
      return true;
   }
   return false;
}   

/* 
 readBoard reads the input of the location of the mines and safe locations
 and stores the values inside an array.
 Precondition: the input values must be either -1 or 9.
*/
void readBoard(int board[][COL], int m, int n) {
   int i,j;
   for(i=0; i<m; i++) {
      for(j=0; j<n; j++) {
         scanf("%d", &board[i][j]);
      }
   }
}

/* 
 printBoard prints the minesweeper board. "*" represents mines 
 and "." represents safe locations. Numbers from 0 to 8 represents
 the number of mines present in the neighbouring cells.
*/
void printBoard(int board[][COL], int m, int n) {
   int i, j;
   for(i=0; i<m; i++) {
      for(j=0; j<n; j++) {
         if(board[i][j] == -1) {
            printf(".");
         }
         else if( board[i][j] >= 9) {
            printf("*");
         } else {
            printf("%d", board[i][j]);
         }
      }
      printf("\n");
   }
}

/* 
  countNeighbour checks the specified location for neighbouring mines,
  returns the number of mines present. P.S: I hard coded this part during the lab
  so I had no choice but to leave it as it is.
  Precondition: the specified location is inside the board
*/
int countNeighbour(int board[][COL], int r, int c, int m, int n) {
   if(board[r][c]!=-1) return board[r][c]; //returns if the location contains a mine or it has been checked
   
   if(isValid(r-1,c,m,n) && board[r-1][c] == 9) {
      board[r][c]++;
   }  
   if(isValid(r-1,c-1,m,n) && board[r-1][c-1] == 9) {
      board[r][c]++;
   }
   if(isValid(r,c-1,m,n) && board[r][c-1] == 9) {
      board[r][c]++;
   }
   if(isValid(r+1,c+1,m,n) && board[r+1][c+1] == 9) {
      board[r][c]++;
   }
   if(isValid(r,c+1,m,n) && board[r][c+1] == 9) {
      board[r][c]++;
   }
   if(isValid(r+1,c,m,n) && board[r+1][c] == 9) {
      board[r][c]++;
   }
   if(isValid(r+1,c-1,m,n) && board[r+1][c-1] == 9) {
      board[r][c]++;
   }
   if(isValid(r-1,c+1,m,n) && board[r-1][c+1] == 9) {
      board[r][c]++;
   }

   board[r][c]++; //since safe locations are denoted by -1, increments regardless of mines' presence.
   return board[r][c];
}

/* 
 clearNeighbours clear neighbouring cells, while making sure
 that they are inside the board. Calls itself repeatedly until
 all possible neighboring cells are cleared
 Precondition: the input location must be a safe location.
*/
void clearNeighbours(int board[][COL], int r, int c, int m, int n) {
   int row[] = {1,0,-1,0,1,1,-1,-1}; //temp array to check all 8 neighbouring cells row
   int col[] = {0,1,0,-1,1,-1,1,-1}; //temp array to check the column
   int i;

   countNeighbour(board,r,c,m,n);
   if(board[r][c] != 8) return;  
   for(i = 0;i<8;i++) { //loop terminates if all neighboring safe cells are cleared 
      int nextRow =  r + row[i], nextCol = c + col[i];
      if(isValid(nextRow,nextCol,m,n) && board[r][c] == -1) {
         clearNeighbours(board,nextRow,nextCol,m,n); //clears the safe cells repeatedly
      }
   }
} 

推荐答案

您需要了解 C数组是零基础

意味着在大小为30的数组中，有效索引是从0到29.

因为你不明白这一点，所以你在计算董事会以外的邻居。

你只要它使用有缺陷的子程序，就无法判断递归部分是否正常工作。



使用调试器应该可以帮助检查发生了什么。



有一个工具可以让你看到你的代码在做什么，它的名字是调试器。它也是一个很好的学习工具，因为它向你展示了现实，你可以看到哪种期望与现实相符。

当你不明白你的代码在做什么或为什么它做它做的时候，答案就是答案是调试器。

使用调试器查看代码正在执行的操作。只需设置断点并查看代码执行情况，调试器允许您逐行执行第1行并在执行时检查变量。



调试器 - 维基百科，免费的百科全书 [ ^ ]



掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]

使用Visual Studio 2010进行基本调试 - YouTube [ ^ ]

调试器在这里向您展示您的代码正在做什么，您的任务是与什么进行比较应该这样做。

调试器中没有魔法，它没有找到错误，它只是帮助你。当代码没有达到预期效果时，你就接近了一个错误。

[更新]

You need to understand that C arrays are zero based
This means that in an array of size 30, valid indexes are from 0 to 29.
Because you did not understood this, you are counting neighbors outside of the board.
You can not tell if recursive part is working or not as long as it use buggy subroutines.

Using the debugger should be great help to check what is going on.

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
[Update]

Quote：

我不认为这是真的，因为我已经实现了isValid函数来检查数组是否超出范围。我相信我的递归实现有错误

I don't think that's true as I have implemented the isValid function to check whether the array is out of bounds or not. I believe there is an error in my implementation of the recursion

不要想，不要相信，使用调试器并确保。

Don't think, don't believe, use the debugger and make sure.

这篇关于如何在这个扫雷程序中实现递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！