找到你要的答案

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

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

Alright so i was implementing a solution of a problem which started of by giving you a (n,n) grid. It required me to to start at (1,1), visit certain points in the grid, marked as * and then finally proceed to (n,n). The size of the grid is guaranteed to be not more then 15 and the number of points to visit , * is guaranteed to be >=0 and <=n-2. The start and end points are always empty. There are certain obstacles , # where I cannot step on. Also, if i have visited a point before reaching a certain *, i can go through it again after collecting *.

Here is what my solution does. I made a datastructure called 'Node' which has 2 integer datatypes (x,y). It's basically a tuple.

 class Node
    {
        int x,y;
        Node(int x1,int y1)
        {
            x=x1;
            y=y1;
        }
    }

While taking in the grid, i maintain a Set which stores the coordinates of '*' in the grid.

Set<Node> points=new HashSet<Node>();

I maintain a grid array and also a distance array

char [][]
int distances [][]

Now what i do is, i apply BFS as (1,1) as source. As soon as i encounter any '*' ( Which i believe will be the closest because BFS provides us with the shortest path in an unweighted graph ), I remove it from the Set.

Now i apply BFS again where my source becomes the last coordinate of '*' found. Everytime, i refresh the distance array since my source coordinate has changed. For the grid array, i refresh the paths marked as 'V' (visited) for the previous iteration.

This entire process continues until i reach the last '*'. BTW if my BFS returns -1, the program prints '-1' and quits.

Now if I have successfully reached all '' in the shortest possible way(i guess?), i set the (n,n) coordinate in the Grid as '' and apply BFS one last time. This way i get to the final point.

Now my solution seemd to be failing somewhere. Have gone wrong somewhere? Is my concept wrong? Does this 'greedy' approach fail? Getting the shortest path between all '*' checkpoints should eventually get me the shortest path IMO.

I looked around and saw this this problem is similar to the Travelling Salesman problem and also solvable by Dynamic Programming and DFS mix or A* algorithm.I have no clue how though. Someone even said dijkstra between each * but according to my knowledge, in an unweighted graph, Dijktra and BFS work the same. I just want to know why this BFS solution fails

Finally, Here is my code:

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;
    }
}

Here is my code in action for a few testcases. Gives the correct answer:

JAVA: http://ideone.com/qoE859

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

Here is where my code fails: http://www.codechef.com/status/N1,bholagabbar

好吧,所以我实现了一个问题的解决方案,开始给你一个(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<Node> points=new HashSet<Node>();

我维护一个网格数组和一个距离数组

char [][]
int distances [][]

现在我所做的是,我申请的是(1,1)作为源。当我遇到任何“*”(我相信这将是最近因为BFS提供加权图的最短路径),我把它从集。

现在我将再次在我的BFS源成为“*”最后的坐标找到。每次,我刷新距离数组,因为我的源坐标已经改变。对于网格数组,我刷新以前的迭代标记为“V”(访问)的路径。

This entire process continues until i reach the last '*'. BTW if my BFS returns -1, the program prints '-1' and quits.

现在,如果我已经成功地达到了'尽可能短的方式'(我猜呢?),我设置了(n,n)坐标网格中的“应用BFS最后一次。这样我到达最后一点。

现在我的解决方案似乎是失败的地方。哪里出了差错?我的观念错了吗?这种“贪婪”的做法失败了吗?让所有的“*”检查点之间的最短路径最终应该得到我最短路径的。

我环顾四周,看到这个问题是类似的旅行商问题,用动态规划解和DFS的混合或A*算法。我不知道怎样。有人甚至说Dijkstra之间*但据我所知,在加权图,Dijkstra和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 /状态/ N1,bholagabbar

answer1: 回答1:

Your idea is wrong. I haven't read the code because what you describe will fail even if implemented perfectly.

Consider something like this:

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

You will traverse the maze like this:

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

Then go from 5 to the bottom-left * and back to 5, taking 16 steps. This however:

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

Takes 12 steps.

The correct solution to the problem involves brute force. Generate all permutations of the * positions, visit them in the order given by the permutation and take the minimum.

13! is rather large though, so this might not be fast enough. There is a faster solution by dynamic programming in O(2^k), similar to the Travelling Salesman Dynamic Programming Solution (also here).

I don't have time to talk about the solution much right now. If you have questions about it, feel free to ask another question and I'm sure someone will chime in (or leave this one open).

你的想法是错误的。我没有读过代码,因为你描述的东西即使完美地执行也会失败。

考虑这样的事情:

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

你会像这样穿过迷宫:

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

然后从5到底部左*和回到5,采取16个步骤。然而这:

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

走12步。

正确的解决方法涉及暴力。生成所有排列的*位置,访问他们在排列的顺序,并采取最低。

13!虽然相当大,所以这可能不够快。有一个更快的解决方案,动态规划在O(2 K K),类似的旅行商动态规划解决方案(也在这里)。

我现在没有时间谈论解决方案。如果你有问题,随时问另一个问题,我相信会有人附和(或离开这一开放)。

algorithm  data-structures  shortest-path  maze  breadth-first-search