- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在通过一本面向初学者的书自学编程。我在 Arrays 章节之后的最后一个任务是:
// Find the biggest area of adjacent numbers in this matrix:
int[][] matrix = {
{1,3,2,2,2,4},
{3,3,3,2,4,4},
{4,3,1,2,3,3}, // --->13 times '3';
{4,3,1,3,3,1},
{4,3,3,3,1,1}
作为提示,我有 - 使用 DFS 或 BFS 算法。在我阅读了它们并看到了它们的许多实现之后,我有了这个想法,但是对于初学者来说这太过分了。我找到了我的任务的解决方案,在多次运行该程序后,我明白了它是如何工作的,现在我可以自己解决问题了。虽然,我很高兴这个解决方案帮助我了解了递归,但我想知道是否可以以迭代方式修改以下代码,如果可以,你能给我提示如何去做吗?提前谢谢你。
public class Practice {
private static boolean[][] visited = new boolean[6][6];
private static int[] dx = {-1,1,0,0};
private static int[] dy = {0,0,-1,1};
private static int newX;
private static int newY;
public static void main(String[] args){
// Find the biggest area of adjacent numbers in this matrix:
int[][] matrix = {
{1,3,2,2,2,4},
{3,3,3,2,4,4},
{4,3,1,2,3,3}, // --->13 times '3';
{4,3,1,3,3,1},
{4,3,3,3,1,1}
};
int current = 0;
int max = 0;
for (int rows = 0; rows < matrix.length;rows++){
for(int cols = 0; cols < matrix[rows].length;cols++){
if (visited[rows][cols] == false){
System.out.printf("Visited[%b] [%d] [%d] %n", visited[rows]
[cols],rows,cols);
current = dfs(matrix,rows,cols,matrix[rows][cols]);
System.out.printf("Current is [%d] %n", current);
if(current > max){
System.out.printf("Max is : %d %n ", current);
max = current;
}
}
}
}
System.out.println(max);
}
static int dfs(int[][] matrix,int x, int y, int value){
if(visited[x][y]){
System.out.printf("Visited[%d][%d] [%b] %n",x,y,visited[x][y]);
return 0;
} else {
visited[x][y] = true;
int best = 0;
int bestX = x;
int bestY = y;
for(int i = 0; i < 4;i++){
//dx = {-1,1,0,0};
//dy = {0,0,-1,1};
int modx = dx[i] + x;
System.out.printf(" modx is : %d %n", modx);
int mody = dy[i] + y;
System.out.printf(" mody is : %d %n", mody);
if( modx == -1 || modx >= matrix.length || mody == -1 || mody >=
matrix[0].length){
continue;
}
if(matrix[modx][mody] == value){
System.out.printf("Value is : %d %n",value);
int v = dfs(matrix,modx,mody,value);
System.out.printf(" v is : %d %n",v);
best += v;
System.out.printf("best is %d %n",best);
}
newX = bestX;
System.out.printf("newX is : %d %n",newX);
newY = bestY;
System.out.printf("newY is : %d %n",newY);
}
System.out.printf("Best + 1 is : %d %n ",best + 1);
return best + 1;
}
}
}
最佳答案
如果您在维基百科页面上查找 Depth-first search在伪代码部分,他们有一个 DFS 算法迭代版本的例子。应该能够从那里找出解决方案。
*编辑
要使其迭代,您可以执行以下操作:
procedure DFS-iterative(matrix, x, y):
let S be a stack
let value = 0
if !visited[v.x, v.y]
S.push(position(x,y))
while S is not empty
Position v = S.pop()
value += 1
for all valid positions newPosition around v
S.push(newPosition)
return value
每次你调用dfs()
递归方法中的方法,你应该调用 S.push()
.您可以按如下方式创建类 Position
class Position{
int x;
int y;
public Position(int x, int y){
this.x = x;
this.y = y;
}
//getters and setters omitted for brevity
}
并使用内置的java类java.util.Stack
让它变得简单。
Stack<Position> s = new Stack<Position>();
如果您想使用 BFS 而不是 DFS,您可以简单地将 Stack 更改为 Queue,您将获得所需的结果。 This link对堆栈和队列有很好的解释,在您了解该主题时可能会很有用。
关于java - 使用DFS算法查找矩阵中相邻数字的最大面积,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44888228/
我正在开发一个企业名录网站,其搜索将由 Google map 驱动。用户将能够根据各种标准搜索他们所在地区的企业,但主要的想法是,如果您搜索例如“新泽西州的水管工”,您将获得新泽西州所有水管工的结果。
我得到了一条任意形状的曲线,包围了一些区域。 我想估计曲线在 iPhone/iPad 屏幕上包围的像素数。我该怎么做? 曲线被定义为点的连续 x/y 坐标。 闭合曲线。 通过用户的触摸(touches
我想删除 R 在点阵图周围的默认边距。这意味着我想摆脱红色矩形之外的所有空白。这是示例: library (raster) library(rasterVis) f <- system.file("e
无法找到任何直接的解决方案来计算 GMSPolygon 对象面积。有什么方法可以做到这一点,或者我必须用边长和一些数学计算来计算它? 最佳答案 感谢@Larme; GMSGeometryArea 就是
假设例如我想将标准正态分布的密度曲线下方的面积着色为十分。我希望最左边 10% 的区域具有与接下来的 10% 不同的阴影,依此类推。 这是问题“Shading a kernel density plo
我正在为 Extjs 开发一个混合图表组件,并且曲线太尖锐了。我找不到曲线具有半径的配置。如果你处理过类似的事情,你能提供一些方法让我的曲线变得平滑一点吗?这是我的代码: Ext.define('Ex
上下文 我有一个 3D 对象,我有它的坐标。然后我将对象旋转 n 次,当对象投影到网格上时,我想计算对象的 2D 面积(以纳米为单位)。 例如, 我在下面有一张图片描述了我的问题。我有相同的对象,但在
当我知道我需要的地 block 总数并且我希望排列是一个正方形(可能有一些空的子地 block )时,我正在尝试弄清楚如何计算子地 block 尺寸。 例如,如果我需要 22 个子图,那么我会为总共
我是一名数据科学家。主要使用Python和SQL来编写代码。我使用data studio进行可视化。所以我对JS不熟悉。我的诀窍data studio community visualizations
我有 1797 张 Mnist 图像,为此我需要提取两个特征(FilledArea、EulerNumber)。我知道如何在 Matlab 中做到这一点。我的特征矩阵在 Matlab 中具有(并且是正确
我希望能够在 Google map 上绘制形状(圆形、多边形和矩形),但我想限制可以绘制的形状的大小(面积)。因此,以圆圈为例,期望的行为是当用户开始从 map 上的某个点拖动鼠标以形成圆圈时,圆圈会
我是一名优秀的程序员,十分优秀!