英文:
Path finding in a finite grid
问题
我有一个7x7的网格（代表一座城市）。我想要从起始点(x1, y1)出发，前往目标点(x2, y2)，并将路径以多个(x, y)字符串的形式输出，用逗号分隔。我想要使用递归来实现这个，如果路径存在则输出true，否则输出false。我应该如何做？我考虑创建4个方法来检查4个方向。对任何建议我都表示感谢。
目前，我只实现了我的类的构造函数：-
map = new boolean[row][column];
for(int i = 0; i < 7; i++)
{
for(int j = 0; j < 7; j++)
{
map[i][j] = false;
}
}
英文:
I have a 7x7 grid (of a city). I want to travel from a starting point (x1, y1) to a destination point (x2, y2) and show the path as an output in the form of multiple (x, y) strings separated by comas. I want to do this using RECURSION and output true if the path exists and false otherwise.
How should I do that? I'm thinking of making 4 methods that check 4 directions. Any input would be appreciated.
For now, I have just implemented the constructor of my class:-
map = new boolean[row][column];
for(int i = 0; i < 7; i++)
{
for(int j = 0; j < 7; j++)
{
map[i][j] = false;
}
}
答案1
得分: 1
import java.io.PrintStream;
/**
* Dev Parzival
* Date : 27/10/2020 Time : 18:28
* I have a confidence about my life that comes from standing tall on my own two feet.
*/
public class Path {
static PrintStream out=System.out;
static boolean pathfound=false;
//////////Main/////////
public static void main(String $[]){
boolean arr[][]=new boolean[5][5];
for(int i=0;i<arr.length;i++)
for(int j=0;j<arr[0].length;j++) {
if (i==0)
arr[i][j] = true;
if(j==arr[0].length-1)
arr[i][j]=true;
}
travel(arr,0,0,arr.length-1,arr[0].length-1);
if(pathfound)
out.println("Path is found");
else
out.println("Path is not found");
}
static boolean travel(boolean a[][],int r,int c,int targetR,int targetC){
//Target is found
if(r==targetR && c==targetC){
pathfound=true;
}
//South
if(!pathfound && r+1<a.length)
if(a[r+1][c]){
a[r+1][c]=false;
pathfound=travel(a,r+1,c,targetR,targetC);
}
//North
if(!pathfound && r-1>=0)
if(a[r-1][c]){
a[r-1][c]=false;
pathfound=travel(a,r-1,c,targetR,targetC);
}
//East
if(!pathfound && c+1<a[0].length)
if(a[r][c+1]){
a[r][c+1]=false;
pathfound=travel(a,r,c+1,targetR,targetC);
}
//West
if(!pathfound && c-1>=0)
if(a[r][c-1]){
a[r][c-1]=false;
pathfound=travel(a,r,c-1,targetR,targetC);
}
if(pathfound)
out.println(r+" "+c);
return pathfound;
}
}
I will advice make a copy of original array so values will not be modified.
I have tested above code works fine. This approach is known as flood fill. Search more about depth first search in graph.
英文:
import java.io.PrintStream;
/**
* Dev Parzival
* Date : 27/10/2020 Time : 18:28
* I have a confidence about my life that comes from standing tall on my own two feet.
*/
public class Path {
static PrintStream out=System.out;
static boolean pathfound=false;
//////////Main/////////
public static void main(String $[]){
boolean arr[][]=new boolean[5][5];
for(int i=0;i<arr.length;i++)
for(int j=0;j<arr[0].length;j++) {
if (i==0)
arr[i][j] = true;
if(j==arr[0].length-1)
arr[i][j]=true;
}
travel(arr,0,0,arr.length-1,arr[0].length-1);
if(pathfound)
out.println("Path is found");
else
out.println("Path is not found");
}
static boolean travel(boolean a[][],int r,int c,int targetR,int targetC){
//Target is found
if(r==targetR && c==targetC){
pathfound=true;
}
//South
if(!pathfound && r+1<a.length)
if(a[r+1][c]){
a[r+1][c]=false;
pathfound=travel(a,r+1,c,targetR,targetC);
}
//North
if(!pathfound && r-1>=0)
if(a[r-1][c]){
a[r-1][c]=false;
pathfound=travel(a,r-1,c,targetR,targetC);
}
//East
if(!pathfound && c+1<a[0].length)
if(a[r][c+1]){
a[r][c+1]=false;
pathfound=travel(a,r,c+1,targetR,targetC);
}
//West
if(!pathfound && c-1>=0)
if(a[r][c-1]){
a[r][c-1]=false;
pathfound=travel(a,r,c-1,targetR,targetC);
}
if(pathfound)
out.println(r+" "+c);
return pathfound;
}
}
I will advice make a copy of original array so values will not be modified.
I have tested above code works fine .This approach is known as flood fill .Search more about depth first search in graph.
答案2
得分: 0
import java.io.PrintStream;
/**
* Dev Parzival
* Date: 27/10/2020 Time: 18:28
* I have a confidence about my life that comes from standing tall on my own two feet.
*/
public class Path {
static PrintStream out = System.out;
static boolean pathfound = false;
//////////Main/////////
public static void main(String $[]) {
boolean arr[][] = new boolean[5][5];
for (int i = 0; i < arr.length; i++)
for (int j = 0; j < arr[0].length; j++) {
if (i == j)
arr[i][j] = true;
}
travel(arr, 0, 0, arr.length - 1, arr[0].length - 1);
if (pathfound)
out.println("Path is found");
else
out.println("Path is not found");
}
static boolean travel(boolean a[][], int r, int c, int targetR, int targetC) {
// Target is found
if (r == targetR && c == targetC) {
pathfound = true;
}
// South
if (!pathfound && r + 1 < a.length)
if (a[r + 1][c]) {
a[r + 1][c] = false;
pathfound = travel(a, r + 1, c, targetR, targetC);
}
// North
if (!pathfound && r - 1 >= 0)
if (a[r - 1][c]) {
a[r - 1][c] = false;
pathfound = travel(a, r - 1, c, targetR, targetC);
}
// East
if (!pathfound && c + 1 < a[0].length)
if (a[r][c + 1]) {
a[r][c + 1] = false;
pathfound = travel(a, r, c + 1, targetR, targetC);
}
// West
if (!pathfound && c - 1 >= 0)
if (a[r][c - 1]) {
a[r][c - 1] = false;
pathfound = travel(a, r, c - 1, targetR, targetC);
}
// North-West
if (!pathfound && c - 1 >= 0 && r - 1 >= 0)
if (a[r - 1][c - 1]) {
a[r - 1][c - 1] = false;
pathfound = travel(a, r - 1, c - 1, targetR, targetC);
}
// Noth-East
if (!pathfound && c + 1 < a[0].length && r - 1 >= 0)
if (a[r - 1][c + 1]) {
a[r - 1][c + 1] = false;
pathfound = travel(a, r - 1, c + 1, targetR, targetC);
}
// South-East
if (!pathfound && c + 1 < a[0].length && r + 1 < a.length)
if (a[r + 1][c + 1]) {
a[r + 1][c + 1] = false;
pathfound = travel(a, r + 1, c + 1, targetR, targetC);
}
// South-West
if (!pathfound && c - 1 >= 0 && r + 1 < a.length)
if (a[r + 1][c - 1]) {
a[r + 1][c - 1] = false;
pathfound = travel(a, r + 1, c - 1, targetR, targetC);
}
// Print the cell position
if (pathfound)
out.println(r + " " + c);
return pathfound;
}
}
Output generated:
4 4
3 3
2 2
1 1
0 0
Path is found
英文:
import java.io.PrintStream;
/**
* Dev Parzival
* Date : 27/10/2020 Time : 18:28
* I have a confidence about my life that comes from standing tall on my own two feet.
*/
public class Path {
static PrintStream out=System.out;
static boolean pathfound=false;
//////////Main/////////
public static void main(String $[]){
boolean arr[][]=new boolean[5][5];
for(int i=0;i<arr.length;i++)
for(int j=0;j<arr[0].length;j++) {
if (i==j)
arr[i][j] = true;
// if(j==arr[0].length-1)
// arr[i][j]=true;
}
travel(arr,0,0,arr.length-1,arr[0].length-1);
if(pathfound)
out.println("Path is found");
else
out.println("Path is not found");
}
static boolean travel(boolean a[][],int r,int c,int targetR,int targetC){
//Target is found
if(r==targetR && c==targetC){
pathfound=true;
}
//South
if(!pathfound && r+1<a.length)
if(a[r+1][c]){
a[r+1][c]=false;
pathfound=travel(a,r+1,c,targetR,targetC);
}
//North
if(!pathfound && r-1>=0)
if(a[r-1][c]){
a[r-1][c]=false;
pathfound=travel(a,r-1,c,targetR,targetC);
}
//East
if(!pathfound && c+1<a[0].length)
if(a[r][c+1]){
a[r][c+1]=false;
pathfound=travel(a,r,c+1,targetR,targetC);
}
//West
if(!pathfound && c-1>=0)
if(a[r][c-1]){
a[r][c-1]=false;
pathfound=travel(a,r,c-1,targetR,targetC);
}
//North-West
if(!pathfound && c-1>=0 && r-1>=0)
if(a[r-1][c-1]){
a[r-1][c-1]=false;
pathfound=travel(a,r-1,c-1,targetR,targetC);
}
//Noth-East
if(!pathfound && c+1<a[0].length && r-1>=0)
if(a[r-1][c+1]){
a[r-1][c+1]=false;
pathfound=travel(a,r-1,c+1,targetR,targetC);
}
//South-East
if(!pathfound && c+1<a[0].length && r+1<a.length)
if(a[r+1][c+1]){
a[r+1][c+1]=false;
pathfound=travel(a,r+1,c+1,targetR,targetC);
}
//South-West
if(!pathfound && c-1>=0 && r+1<a.length)
if(a[r+1][c-1]){
a[r+1][c-1]=false;
pathfound=travel(a,r+1,c-1,targetR,targetC);
}
//Print the cell position
if(pathfound)
out.println(r+" "+c);
return pathfound;
}
}
Above code will find a path between starting cell and the destination cell if path exists.
Output it generates:
4 4
3 3
2 2
1 1
0 0
Path is found
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论