在使用 BFS 到达目的地之前访问网格中的选定点

Question

好吧，我正在实施一个问题的解决方案，首先是给你一个 (n,n) 网格。它要求我从 (1,1) 开始，访问网格中标记为 * 的某些点，然后最后进行到 (n,n)。网格的大小保证不超过 15，访问的点数 * 保证 >=0 且 <=n-2。起点和终点始终为空。有一些障碍，#我不能踩的地方。此外，如果我在到达某个 * 之前访问过某个点，我可以在收集 * 后再次通过它。

这是我的解决方案的作用。我创建了一个名为 'Node' 的数据结构，它有 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 returns -1，程序会打印“-1”并退出。

现在，如果我以尽可能短的方式成功到达所有“”（我猜？），我将网格中的 (n,n) 坐标设置为“”最后一次应用 BFS。这样我就到了最后一点。

现在我的解决方案似乎在某处失败了。哪里出错了？我的概念错了吗？这种 'greedy' 方法会失败吗？获得所有“*”检查点之间的最短路径最终应该让我得到最短路径 IMO。

我环顾四周，看到这个问题类似于旅行商问题，也可以通过动态规划和 DFS 混合或 A* 解决 algorithm.I 不知道如何解决。有人甚至在每个 * 之间说 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;
    }
}

这是我的几个测试用例的代码。给出正确答案：

JAVA: http://ideone.com/qoE859

C++ : http://ideone.com/gsCSSL

这是我的代码失败的地方：http://www.codechef.com/status/N1,bholagabbar

Answer 1

你的想法是错误的。我没有读过代码，因为你描述的即使完美实现也会失败。

考虑这样的事情：

x....
.....
..***
....*
*...*

您将像这样穿越迷宫：

x....
.....
..123
....4
*...5

然后从 5 到左下 * 并返回 5，走 16 步。然而，这：

x....
.....
..234
....5
1...6

走 12 步。

问题的正确解法涉及蛮力。生成*个位置的所有排列，按照排列给出的顺序访问它们，取最小的。

13! 相当大，所以这可能不够快。在 O(2^k) 中有一个更快的动态规划解决方案，类似于 Travelling Salesman Dynamic Programming Solution (also here).

我现在没有时间谈论解决方案。如果您对此有任何疑问，请随时提出另一个问题，我相信有人会插话（或让这个问题保持开放状态）。

在使用 BFS 到达目的地之前访问网格中的选定点

Visiting Selected Points in a Grid before Reaching a Destination using BFS

algorithm

data-structures

shortest-path

maze

breadth-first-search