通过从点向外扩展进行矩阵遍历? [英] Matrix Traversal by expanding outwards from a point?
问题描述
对不起，标题不清楚.我不确定如何在没有示例的情况下使用它.因此，目标是从单个点开始(可能在矩阵中的任何位置)时，尽可能快地在所有方向上遍历矩阵.我的想法是使用2D阵列，从该点向各个方向向外扩展，就像爆炸一样.在开发这种算法时，我遇到的问题是，当像素向外扩展并探索已经探索的像素时，它变得非常低效.这是我想做的一个例子.
Sorry if the title isn't clear. I wasn't sure how to phrase it without an example. So the goal is to traverse a matrix in all directions as fast as possible when starting at a single point(could be anywhere in the matrix). My idea was to use a 2D array and expand outwards in all directions from that single point almost like an explosion. The problem I ran into when developing such an algorithm is that it becomes wildly inefficient when pixels are expanding outwards and exploring already explored pixels. Here is an example of what I would like to do.
0,0,0,0,0
0,0,0,0,0
0,0,1,0,0
0,0,0,0,0
0,0,0,0,0
0,0,0,0,0
0,0,1,0,0
0,1,1,1,0
0,0,1,0,0
0,0,0,0,0
0,0,1,0,0
0,1,1,1,0
1,1,1,1,1
0,1,1,1,0
0,0,1,0,0
1,1,1,1,1
1,1,1,1,1
1,1,1,1,1
1,1,1,1,1
1,1,1,1,1
谢谢您能给我的任何帮助！
Thank you for any help you can give me!
推荐答案
请考虑以下示例(注释说明):
import java.util.ArrayList;
public class MatrixTraversal {
public static void main(String[] main){
// 5x5 matrix example
Byte[][] matrix = {{0,0,0,0,0},{0,0,0,0,0},
{0,0,0,0,0},{0,0,0,0,0},
{0,0,0,0,0}};
// testing
expand(matrix, new Point(0,0));
print(matrix);
expand(matrix, new Point(2,4));
print(matrix);
expand(matrix, new Point(4,1));
print(matrix);
expand(matrix, new Point(3,1));
print(matrix);
expand(matrix, new Point(2,2));
print(matrix);
}
////////////////////////////////////////////////////////
/**
* This method to expand a given point in the matrix
* @param matrix
* @param point
*/
public static void expand(Byte[][]matrix, Point point){
// first change the given point to 1
matrix[point.x][point.y]=1;
// then get the neighbors points of the given point
ArrayList<Point> neighbors = neighbors(matrix, point);
// loop through the neighbors ArrayList and convert
// the corresponding points to 1's
for(Point p : neighbors){
matrix[p.x][p.y]=1;
}
}
////////////////////////////////////////////////////////
/**
* This method to return the VALID neighbors points of
* a given point in the matrix
* @param matrix
* @param point
*/
public static ArrayList<Point> neighbors(Byte[][]matrix, Point point){
int column = point.y; int row = point.x;
ArrayList<Point> neighbors = new ArrayList<Point>();
if(column>0){
if(matrix[row][column-1]!=1){
neighbors.add(new Point(row, column-1));
}
}
if(column<matrix[0].length-1){
if(matrix[row][column+1]!=1){
neighbors.add(new Point(row, column+1));
}
}
if(row>0){
if(matrix[row-1][column]!=1){
neighbors.add(new Point(row-1, column));
}
}
if(row<matrix.length-1){
if(matrix[row+1][column]!=1){
neighbors.add(new Point(row+1, column));
}
}
return neighbors;
}
////////////////////////////////////////////////////////
/**
* This method just to print the result
* @param matrix
*/
public static void print(Byte[][] matrix){
for(int i=0; i< matrix.length; i++, System.out.println()){
for(int j=0; j< matrix[0].length; j++){
System.out.print(matrix[i][j] + " ");
}
}
System.out.println("---------");
}
////////////////////////////////////////////////////////
//Inner Class to represent a Point(x,y)
public static class Point{
int x,y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
}
测试
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
---------
1 1 0 0 0
1 0 0 0 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
---------
1 1 0 0 0
1 0 0 0 1
0 0 0 1 1
0 1 0 0 1
1 1 1 0 0
---------
1 1 0 0 0
1 0 0 0 1
0 1 0 1 1
1 1 1 0 1
1 1 1 0 0
---------
1 1 0 0 0
1 0 1 0 1
0 1 1 1 1
1 1 1 0 1
1 1 1 0 0
这篇关于通过从点向外扩展进行矩阵遍历?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
