查找路径是否存在于覆盖有相同半径的圆的网格中

Question

我在面试中被问到这个问题，我无法解决。

如果您能帮我解决，我将不胜感激。

问题如下：-

给定一个矩形区域，其左侧和底部坐标为(0,0 ) 和最右和最上坐标是 (x,y)。

区域内有 n 个具有给定圆心坐标的圆，它们都具有相同的半径 'r'。

您目前正站在 (0,0) 并且想要到达 (x,y) 而不触及任何圆圈。

你必须告诉它是否可能。

他告诉我你可以在2点之间自由移动，不需要沿着x轴或y轴移动 .

我想到的解决方案涉及采用 x*y 维度的矩阵，并为每个圆圈标记位于其中的点或触摸它。

之后应用BFS从(0,0)开始检查我们是否可以达到(x,y).

他告诉我 BFS 会错，我不明白为什么。

我假设圆有 整数半径 并且有 整数坐标 。

他还让我在没有这些假设的情况下解决这个问题。

我做不到。当被问及时，他告诉我这是一个标准问题，我应该可以在 google 上找到它。

我又不能。请帮忙！

Answer 1

我认为2个圆圈只有在圆心之间的距离小于2r时才能挡住路径。因此，构建 "islands" 个重叠圆圈并检查是否有任何岛屿阻挡了从 0 到 (x,y) 的路径就足够了，即其中是否有任何圆圈以这样的方式与矩形边界相交，即它们之间的直线那些交叉点会阻塞路径。

Answer 2

如果两个圆接触，在它们的中心之间画一条线段。如果一个圆接触到矩形的边缘，则将其中心连接到最近一侧的投影。然后丢弃圆圈。这不会修改障碍物的连接性，并且您已将问题转化为更熟悉的平面直线细分问题。

一种方法是将域分解为平板，即通过每个中心绘制水平线以将平面划分为梯形。然后通过种子填充方法，可以确定起始板并将可访问性扩展到与其具有公共水平边的板，直到填充封闭区域或到达出口板。

下面是从 top-left 平板填充种子的中间步骤。

如果圆心在规则的网格上，标准种子填充即可。

Answer 3

懒惰方法：

依次访问每个球
- 如果它没有碰到任何其他球，则将其报废。
- 如果它触及另一个，将它和另一个添加到你最喜欢的节点图系统并在它们之间创建一个连接（做一些家务以避免双胞胎）。
创建额外的球 A、B、C、D
在 A 和所有触及左边缘的球之间、B 和所有触及顶部边缘的球之间等创建额外的连接（图中的线）
询问您的 A* 是否愿意导航 您从 A 到 C / A 到 D / B 到 C / B 到 D。
如果以上任何一项是，那么问题的答案是否定的。又快又脏 :-).

Answer 4

解决此问题的最佳方法是使用 dfs 搜索。首先让我们考虑一些基本情况，比如如果存在一个包含两个点（即 0,0 或 x,y）中的任何一个但不是两者都包含的圆，那么答案是 "NO" 并且如果存在一个包含两个点的圆这些点然后我们可以将其从我们的圈子列表中删除。现在我们剩下的圆圈不包含两个点中的任何一个现在使用这些圆圈的中心作为顶点制作图形并连接任何两个顶点如果它们之间的距离小于或等于 2*R 并且还保持所有圆的掩码数组，掩码存储由特定圆切割的边，即如果我们将左侧垂直边编号为 0 顶部水平边为 1 右侧垂直边为 2 底部水平边为 3 然后在对应于特定圆的掩码中这些位将处于活动状态，对应于该圆切割的边。现在只需执行 dfs 并查看图中是否存在一条路径，该路径显示是否可以使用图的边从 0 边移动到 2 边或 0 边到 3 边或 1 边到 2 边或 1 边到 2 边（我们使用面具检查）。如果存在这样的路径，则答案为 "NO"，否则答案始终为 "YES"。

Answer 5

我完全按照安东建议的方式做了这道题。使用 DSU 制作所谓的岛屿。然后确定以下条件：TB,LR,TR,LB (T: Top, B:Bottom, L:Left, R:Right ) 路口。如果任何一个岛屿做出这些交叉点，它们肯定会阻塞路径，答案将是 "NO"。问题可以在 Interview Bit 找到： https://www.interviewbit.com/problems/valid-path/ 并在此给出相应的解决方案：

http://ideone.com/19iSOn

#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;

class Solution{
public:
    string solve(int A, int B, int C, int D, vector<int> &E, vector<int> &F);
};

#define pii pair<int,int>

int par[1000+5];
int rnk[1000+5];
bool vis[1000+5];

void initialise(){
    for(int i=0;i<=1000;i++){
        par[i]=i;
        rnk[i]=1;
        vis[i]=false;
    }
}

int findPar(int node){
    if(par[node]==node)return node;
    return par[node]=findPar(par[node]);
}

void makeUnion(int a,int b){
    int parA=findPar(a);
    int parB=findPar(b);

    if(parA==parB)return;
    if(rnk[parA]<rnk[parB])par[parB]=parA;
    else if(rnk[parB]<rnk[parA])par[parA]=parB;
    else{
        rnk[parA]++;
        par[parB]=parA;
    }
}


bool findBlockage(int root,int X,int Y,int N,int R,vector<pair<int,pii>>vec){
    int top=0;
    int bottom=INT_MAX;
    int left=INT_MAX;
    int right=0;

    for(int i=0;i<N;i++){
        if(par[vec[i].first]==root){
            int x=vec[i].second.first;
            int y=vec[i].second.second;
            top=max(top,y+R);
            bottom=min(bottom,y-R);
            left=min(left,x-R);
            right=max(right,x+R);
        }
    }
    if(top>=Y and bottom<=0)return true;
    if(right>=X and left<=0)return true;
    if(top>=Y and right>=X)return true;
    if(left<=0 and bottom<=0)return true;
    return false;
}

string Solution::solve(int X, int Y, int N, int R, vector<int> &E, vector<int> &F) {
    vector<pair<int,pii>> vec;
    int id=0;
    for(int i=0;i<N;i++){
        vec.push_back({id,{E[i],F[i]}});
        id++;
    }

    initialise();

    for(int i=0;i<N;i++){
        for(int j=i;j<N;j++){
            if(i==j)continue;
            int x1=vec[i].second.first;
            int x2=vec[j].second.first;

            int y1=vec[i].second.second;
            int y2=vec[j].second.second;

            if(((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) <= (4*R*R)){
                makeUnion(vec[i].first,vec[j].first);
            }
        }
    }

    for(int i=0;i<N;i++){
        if(!vis[par[vec[i].first]]){
            vis[par[vec[i].first]]=1;
            bool ret = findBlockage(par[vec[i].first],X,Y,N,R,vec);
            if(ret)return "NO";
        }
    }
    return "YES";
}

int main(){
    int n,x,y,r;
    cin>>x>>y>>n>>r;
    vector<int>X(n);
    vector<int>Y(n);

    for(int i=0;i<n;i++)cin>>X[i];
    for(int i=0;i<n;i++)cin>>Y[i];

    Solution sol;
    cout<<sol.solve(n,x,y,r,X,Y)<<endl;
}

Answer 6

面试官说BFS不能用的地方错了。每当您进入一个单元格时，检查该单元格是否在一个圆圈内，方法是检查该单元格与您可用的每个其他圆心的距离，如果它在 dist<=R 内，则无法从当前的特定单元格。我解决了 interviewbit 中存在的类似问题 - https://www.interviewbit.com/problems/valid-path/ 代码很简单 -

   public class Solution {
private class Pair
{
    int x ; int y ;
}
ArrayList<Integer> xindex ; ArrayList<Integer> yindex ; int R ;int len ;
public String solve(int x, int y, int n, int r, ArrayList<Integer> xi, ArrayList<Integer> yi) {
    int dp[][] = new int[x+1][y+1] ;
    len = xi.size() ;
    for(int i=0;i<=x;i++)
    {
        for(int j=0;j<=y;j++)
        dp[i][j] = -1 ;
    }

    xindex = xi ; yindex = yi ;
    dp[0][0] = 1 ; R = r*r ;
    LinkedList<Pair> q = new LinkedList<Pair>() ;
    Pair obj = new Pair() ;
    obj.x = 0 ; obj.y = 0 ;
    q.add(obj) ;
    int arr1[] = {1,1,1,0,-1,-1,-1,0} ;
    int arr2[] = {-1,0,1,1,1,0,-1,-1} ;

    while(q.size()!=0)
    {
        Pair temp = q.poll() ;
        int x1 = temp.x ;
        int x2 = temp.y ;

        for(int i=0;i<8;i++)
        {
            int t1 = x1+arr1[i] ; int t2 = x2+arr2[i] ;

            if((t1>=0)&&(t1<=x)&&(t2>=0)&&(t2<=y))
            {
                if(dp[t1][t2]==-1)
                {
                    boolean res = isValidIndex(t1,t2) ;
                    if(res==false)
                    dp[t1][t2] = 2 ;
                    else
                    {
                        dp[t1][t2] = 1 ;
                        Pair t = new Pair() ;
                        t.x = t1 ; 
                        t.y = t2 ;
                        q.add(t) ;
                    }
                }
            }
        }

        if(dp[x][y]!=-1)
        break ;
    }

    if(dp[x][y]==1)
    return "YES" ;

    return "NO" ;

}

public boolean isValidIndex(int x,int y)
{
    for(int i=0;i<len;i++)
    {
        int x1 = xindex.get(i) ; int x2 = yindex.get(i) ;
        if((x==x1)&&(y==x2))
        return false ;

        int n = (x1-x)*(x1-x) + (x2-y)*(x2-y) ;

        if(n<=R)
        return false ;
    }
    return true ;
}

}

Answer 7

一个递归解决这个问题（找到从[0,0]到[x,y]的路径，用圆圈作为障碍物），使用简单的DP概念：

public class Solution {
    public long radiusSquare;
    public int xDest, yDest;
    boolean vis[][];
    public final static int[] xDelta = new int[]{0, 1, -1, 0, 1, -1, -1, 1};
    public final static int[] yDelta = new int[]{1, 0, 0, -1, 1, -1, 1, -1};

    public String solve(int x, int y, int radius, ArrayList<Integer> X, ArrayList<Integer> Y) {
        xDest = x; yDest = y;
        radiusSquare = radius*radius;
        int dp[][] = new int[x+1][y+1]; // = 0 (not visited), = 1 (a valid point), = 2 (invalid)
        vis = new boolean[x+1][y+1];
        if (recur(0, 0, X, Y, dp)) return "YES";
        return "NO";
    }
    public boolean recur(int xi, int yi, ArrayList<Integer> X, 
                         ArrayList<Integer> Y, int dp[][]){
        if (xi == xDest && yi == yDest) return true;
        if(vis[xi][yi]) return false; // already processed coordinate
        vis[xi][yi] = true;
        for (int i =0; i < xDelta.length; i++){
            int xArg = xi+xDelta[i];
            int yArg = yi+yDelta[i];
            if (validCoordinates(xArg, yArg, X, Y, dp) && recur(xArg, yArg, X, Y, dp)) 
                return true;
        }
        return false;
    }
    public boolean validCoordinates(int x, int y, ArrayList<Integer> X, ArrayList<Integer> Y, int dp[][]){
        if (x < 0 || y < 0 || x > xDest || y > yDest) return false;

        if (dp[x][y] != 0){
            if (dp[x][y] == 1) return true; // valid coord 
            if (dp[x][y] == 2) return false;
        } 

        for (int i = 0; i < X.size(); i++){ // loop through each circle.
            long sumOfSquare = ((x-X.get(i))*(x-X.get(i))) + ((y-Y.get(i))*(y-Y.get(i)));
            if (sumOfSquare <= radiusSquare){
                dp[x][y] = 2; // comes on or inside circle
                return false;
            }
        }
        dp[x][y] = 1;
        return true;
    }
}

查找路径是否存在于覆盖有相同半径的圆的网格中

Find if a path exists in a grid covered with circles of same radius

algorithm

geometry

dynamic-programming

computational-geometry