基本上这是一项家庭作业，如果你回答我的问题，我更喜欢得到答案的线索，而不是代码和答案本身。
这必须是一种递归方法，在给定的二维布尔数组中，它必须返回数组中真实区域的数量——数组中的行和列的数量始终相同。
当至少有一个真元素时，就会定义真区域，如果它有一个相邻的其他元素也是真的，它们仍然算作1。对角线元素不被视为邻居。
例如，在这个矩阵中，当1为真，0为假时，有3个真区——左侧的两个单元格，右侧的三个单元格，以及最后一行的一个单元格。
1 0 0 1
1 0 1 1
0 1 0 0
我不知道如何递归地处理这个问题，在一个简单的迭代中，我认为它会很简单，但似乎不可能使用调用自己的方法来检查数组。
有人有线索吗？
这些本质上是连接的组件，使用DFS。
既不优雅也不高性能，我的第一次尝试是尝试通过递归模拟所有字段的迭代，如果每个字段是真区域，则返回1。同时传递一个数组以跟踪已选中的字段。对子调用的结果求和。
// spoiler alert
public class Minefield {
public static void main(String[] args) throws Exception {
int[][] field = { //
{ 1, 0, 0, 1 }, //
{ 1, 0, 1, 1 }, //
{ 0, 1, 0, 0 }, //
};
int w = field[0].length;
int h = field.length;
int count = count(0, 0, w, h, true, field, new int[h][w]);
System.out.println("true zones: " + count);
}
private static int count(int x, int y, int w, int h, boolean checkForNewZone /* false: mark zone */, int[][] field, int[][] marked) {
if(x < 0 || x >= w || y < 0 || y >= h) {
return /* out of bounds */ 0;
}
if(checkForNewZone) {
int count = 0;
if(field[y][x] == 1 && marked[y][x] == 0) {
// a new true zone -> count it
count++;
// and mark it
count(x, y, w, h, false, field, marked);
}
// iterate to the next field
// x++;
// if(x >= w) {
// x = 0;
// y++;
// }
// count += count(x, y, w, h, true, field, marked);
// check neighboring fields (right & down should cover everything, assuming the starting point is the top left)
count += count(x + 1, y, w, h, true, field, marked);
count += count(x, y + 1, w, h, true, field, marked);
return count;
}
else {
// mark zone
if(field[y][x] == 1 && marked[y][x] == 0) {
marked[y][x] = 1;
count(x + 1, y, w, h, false, field, marked);
count(x - 1, y, w, h, false, field, marked);
count(x, y + 1, w, h, false, field, marked);
count(x, y - 1, w, h, false, field, marked);
}
return 0;
}
}
}
典型的递归算法由两部分组成：
- 一个基本情况
- 一个"；感应步骤">
从确定基本情况开始。这些可能通过输入数组的大小来识别。例如，0x0阵列没有真正的区域有时有多个基本情况
然后确定如何在给定较小版本的输入的答案的情况下，计算较大版本输入的答案。这可能看起来像是在考虑如何从分区数为Z的nxm阵列到分区数为Z'的(n+1(xm阵列和分区数为Z'的nx(m+1(阵列通常有必要解决稍微复杂一点的问题才能成功，因为你可以对较小的输入假设更多的答案
通常很容易将这两种情况转换为递归程序。