类似扫雷游戏的回溯递归,二维布尔数组

carvr3hs  于 2021-06-27  发布在  Java
关注(0)|答案(3)|浏览(314)

基本上这是一个家庭作业,如果你回答我的问题,祝福你,我宁愿得到一个答案,而不是代码和答案本身的线索。
这必须是一个递归方法,在给定的二维布尔数组中,该方法必须返回数组中的真区域数-数组中的行数和列数将始终相同。
当至少有一个真元素时,真区域就被定义了,如果它有一个相邻的其他元素也是真的,它们仍然计为1。对角线元素不被视为邻居。
例如,在这个矩阵中,当1表示真,0表示假时,有3个真区域-左边的两个单元格,右边的三个单元格,最后一行的一个单元格,他自己。

  1. 1 0 0 1
  2. 1 0 1 1
  3. 0 1 0 0

我不知道如何递归地处理这个问题,在一个简单的迭代中,我认为这是非常简单的,但是似乎不可能使用一个调用自身的方法来检查数组。
有人有线索吗?

6ie5vjzr

6ie5vjzr1#

我的第一次尝试是尝试通过递归模拟所有字段的迭代,如果每个字段是真区域,则返回1。同时传递数组以跟踪已检查的字段。对子调用的结果求和。

  1. // spoiler alert
  2. public class Minefield {
  3. public static void main(String[] args) throws Exception {
  4. int[][] field = { //
  5. { 1, 0, 0, 1 }, //
  6. { 1, 0, 1, 1 }, //
  7. { 0, 1, 0, 0 }, //
  8. };
  9. int w = field[0].length;
  10. int h = field.length;
  11. int count = count(0, 0, w, h, true, field, new int[h][w]);
  12. System.out.println("true zones: " + count);
  13. }
  14. private static int count(int x, int y, int w, int h, boolean checkForNewZone /* false: mark zone */, int[][] field, int[][] marked) {
  15. if(x < 0 || x >= w || y < 0 || y >= h) {
  16. return /* out of bounds */ 0;
  17. }
  18. if(checkForNewZone) {
  19. int count = 0;
  20. if(field[y][x] == 1 && marked[y][x] == 0) {
  21. // a new true zone -> count it
  22. count++;
  23. // and mark it
  24. count(x, y, w, h, false, field, marked);
  25. }
  26. // iterate to the next field
  27. // x++;
  28. // if(x >= w) {
  29. // x = 0;
  30. // y++;
  31. // }
  32. // count += count(x, y, w, h, true, field, marked);
  33. // check neighboring fields (right & down should cover everything, assuming the starting point is the top left)
  34. count += count(x + 1, y, w, h, true, field, marked);
  35. count += count(x, y + 1, w, h, true, field, marked);
  36. return count;
  37. }
  38. else {
  39. // mark zone
  40. if(field[y][x] == 1 && marked[y][x] == 0) {
  41. marked[y][x] = 1;
  42. count(x + 1, y, w, h, false, field, marked);
  43. count(x - 1, y, w, h, false, field, marked);
  44. count(x, y + 1, w, h, false, field, marked);
  45. count(x, y - 1, w, h, false, field, marked);
  46. }
  47. return 0;
  48. }
  49. }
  50. }
展开查看全部
hwazgwia

hwazgwia2#

这些基本上是连接的组件,请使用dfs。

hts6caw3

hts6caw33#

典型的递归算法由两部分组成:
基本情况
“归纳步骤”
从确定基本情况开始。这些可能由输入数组的大小来识别。e、 例如,0x0数组没有真区域。有时有多个基本情况。
然后确定在给定较小输入版本的答案的情况下,如何计算较大输入版本的答案。这看起来像是在考虑如何从具有z个分区的nxm数组转换为具有z'分区的(n+1)xm数组和具有z'分区的nx(m+1)数组。通常,为了获得成功,需要解决稍微复杂一点的问题,因为你可以对较小的输入假设更多的答案。
通常很容易将这两种情况转换为递归程序。

相关问题