好吧，我正在实现一个问题的解决方案，首先是给你一个 (n,n) 网格。它要求我从 (1,1) 开始，访问网格中标记为 * 的某些点，然后最后进行到 (n,n)。网格的大小保证不超过 15，访问的点数 * 保证 >=0 且 <=n-2。起点和终点始终为空。有一些障碍，#我不能踩的地方。此外，如果我在到达某个 * 之前访问过某个点，我可以在收集 * 后再次通过它。
这是我的解决方案的作用。我制作了一个名为“节点”的数据结构，它有 2 个整数数据类型(x，y)。它基本上是一个元组。
class Node
{
int x,y;
Node(int x1,int y1)
{
x=x1;
y=y1;
}
}
在获取网格时，我维护一个 Set，它存储网格中“*”的坐标。
Set<Node> points=new HashSet<Node>();
我维护了一个网格数组和一个距离数组
char [][]
int distances [][]
现在我要做的是，我将 BFS 应用为 (1,1) 作为源。一旦我遇到任何“*”(我相信这将是最接近的，因为 BFS 为我们提供了未加权图中的最短路径)，我将其从集合中删除。
现在我再次应用 BFS，我的源成为找到的“*”的最后一个坐标。每次，我都会刷新距离数组，因为我的源坐标发生了变化。对于网格阵列，我为上一次迭代刷新标记为“V”(已访问)的路径。
整个过程一直持续到我到达最后一个“*”。 顺便说一句，如果我的 BFS 返回 -1，程序会打印“-1”并退出。
现在，如果我以尽可能短的方式成功到达所有“”(我猜？)，我将网格中的 (n,n) 坐标设置为“”并最后应用 BFS时间。这样我就到了最后一点。
现在我的解决方案似乎在某处失败了。哪里出错了？我的概念错了吗？这种“贪婪”的方法会失败吗？获得所有“*”检查点之间的最短路径最终应该让我得到最短路径 IMO。
我环顾四周，发现这个问题类似于旅行商问题，也可以通过动态规划和 DFS 混合或 A* 算法解决。但我不知道如何解决。有人甚至在每个 * 之间说 dijkstra，但据我所知，在未加权的图中，Dijktra 和 BFS 的工作原理相同。我只想知道为什么这个 BFS 解决方案失败
最后，这是我的代码:
import java.io.*;
import java.util.*;
/**
* Created by Shreyans on 5/2/2015 at 2:29 PM using IntelliJ IDEA (Fast IO Template)
*/
//ADD PUBLIC FOR CF,TC
class Node
{
int x,y;
Node(int x1,int y1)
{
x=x1;
y=y1;
}
}
class N1
{
//Datastructures and Datatypes used
static char grid[][];
static int distances[][];
static int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
static int dx[]={1,-1,0,0};
static int dy[]={0,0,-1,1};
static Set<Node> points=new HashSet<Node>();
static int flag=1;
public static void main(String[] args) throws IOException
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();//testcases
for(int ixx=0;ixx<t;ixx++)
{
flag=1;
r=sc.nextInt();
if(r==1)
{
sc.next();//Taking in '.' basically
System.out.println("0");//Already there
continue;
}
c=r;//Rows guarenteed to be same as rows. It a nxn grid
grid=new char[r][c];
distances=new int[r][c];
points.clear();
for(int i=0;i<r;i++)
{
char[]x1=sc.next().toCharArray();
for(int j=0;j<c;j++)
{
grid[i][j]=x1[j];
if(x1[j]=='*')
{
points.add(new Node(i,j));
}
}
}//built grid
s1=s2=0;
distances[s1][s2]=0;//for 0,0
int ansd=0;
while(!points.isEmpty())
{
for(int i=0;i<r;i++)
{
for (int j = 0; j < c; j++)
{
distances[i][j]=0;
if(grid[i][j]=='V')//Visited
{
grid[i][j]='.';
}
}
}
distances[s1][s2]=0;
int dis=BFS();
if(dis!=-1)
{
ansd += dis;//Adding on (minimum?) distaces
//System.out.println("CURR DIS: "+ansd);
}
else
{
System.out.println("-1");
flag = 0;
break;
}
}
if(flag==1)
{
for(int i11=0;i11<r;i11++)
{
for(int j1=0;j1<c;j1++)
{
if(grid[i11][j1]=='V')//These pnts become accesible in the next iteration again
{
grid[i11][j1]='.';
}
distances[i11][j1]=0;
}
}
f1=r-1;f2=c-1;
grid[f1][f2]='*';
int x=BFS();
if(x!=-1)
{
System.out.println((ansd+x));//Final distance
}
else
{
System.out.println("-1");//Not possible
}
}
}
}
public static int BFS()
{
// Printing current grid correctly according to concept
System.out.println("SOURCE IS:"+(s1+1)+","+(s2+1));
for(int i2=0;i2<r;i2++)
{
for (int j1 = 0; j1 < c; j1++)
{
{
System.out.print(grid[i2][j1]);
}
}
System.out.println();
}
Queue<Node>q=new LinkedList<Node>();
q.add(new Node(s1,s2));
while(!q.isEmpty())
{
Node p=q.poll();
for(int i=0;i<4;i++)
{
if(((p.x+dx[i]>=0)&&(p.x+dx[i]<r))&&((p.y+dy[i]>=0)&&(p.y+dy[i]<c))&&(grid[p.x+dx[i]][p.y+dy[i]]!='#'))
{//If point is in range
int cx,cy;
cx=p.x+dx[i];
cy=p.y+dy[i];
distances[cx][cy]=distances[p.x][p.y]+1;//Distances
if(grid[cx][cy]=='*')//destination
{
for(Node rm:points)// finding the node and removing it
{
if(rm.x==cx&&rm.y==cy)
{
points.remove(rm);
break;
}
}
grid[cx][cy]='.';//It i walkable again
s1=cx;s2=cy;//next source set
return distances[cx][cy];
}
else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
{
grid[cx][cy]='V';//Adding to visited
q.add(new Node(cx,cy));
}
}
}
}
return -1;
}
}
这是我的几个测试用例的代码。给出正确答案:
这是我的代码失败的地方:http://www.codechef.com/status/N1,bholagabbar
最佳答案
你的想法是错误的。我没有阅读代码，因为即使完美实现，您描述的内容也会失败。
考虑这样的事情:
x....
.....
..***
....*
*...*
你将像这样穿越迷宫:
x....
.....
..123
....4
*...5
然后从 5 到左下角的 * 并返回到 5，走 16 步。然而，这:
x....
.....
..234
....5
1...6
需要 12 步。
问题的正确解决方案涉及蛮力。生成*位置的所有排列，按照排列给定的顺序访问它们，取最小值。
13! 相当大，所以这可能不够快。 O(2^k) 中的动态规划有一个更快的解决方案，类似于 Travelling Salesman Dynamic Programming Solution (还有 here )。
我现在没有时间过多讨论解决方案。如果您对此有任何疑问，请随时提出另一个问题，我相信有人会插话(或让这个问题保持开放状态)。
关于algorithm - 在使用 BFS 到达目的地之前访问网格中的选定点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30002930/