检查是否存在圆

Question

我在 Google 采访中被问到这个问题。我们得到一个由字母 F、L、R 组成的字符串。 - 这是机器人遵循的指令

F-前进一步

L-左转

R-右转

字符串长度最多为 2500 个字符。

字符串自身运行无限次。我们需要判断是否存在一个半径为 r（r 可以是任何实数）的圆，这样机器人就不会离开圆。我被困在这个 point.I 使用凸包的想法上，但是如何用代码检查它是否无限 times.Explanation 将不胜感激。请帮忙。提前致谢

Answer 1

运行字符串，看机器人在哪一端，看向哪个方向

如果它回到了原点，取它在执行过程中与原点的最大距离并与 r 进行比较。

如果没有回到原点，则检查它的方向：

如果它和开始的方向相同，那么它会无限期地远离原点，所以不存在这样的r。

如果它的方向与开始时不同，那么在字符串迭代 4 或 2 次后它将 return 到原点，具体取决于它是否朝向 left/right 其原始方向，或它的反向，分别。现在取字符串执行 2 次后的最大距离。（简单的区分大小写，不管周期是2次还是4次，执行2次就到最大距离了。）

Answer 2

每个运行（一个运行执行给定字符串的所有命令一次）改变两件事：机器人注视的方向和它的位置（即每个运行将它移动一些向量（这个向量的方向取决于它在运行之前的初始方向）并旋转它）。
可能的方向数为4。因此，在运行模拟4次后，它看起来与最初的方向相同（每次摩擦都会旋转相同的角度).
这就是为什么 4 个连续的运行只是将它移动某个矢量而不进行任何旋转。
这样，我们就可以连续运行模拟4次，看是否停在原点。如果是，我们可以找到包含其路径的最小圆。否则，不存在这样的圈子。

Answer 3

您需要运行 1 次迭代来计算新位置，例如 newx、newy。然后你会计算 4 次以上的迭代，看看机器人是否回到了 newx-newy。如果是，则圆存在，否则不存在。

半径将是机器人在迭代中冒险走出的最大距离。

代码实现 -

//North, South, East, West directions
#define N 0 
#define S 1
#define E 2
#define W 3

// Function to compute the new pos (x, y, dir) after completing one iteration of the string.
// It will also update the max radius.
void findNewPos(char *str, int *origdir, int *origx, int *origy, double *maxrad) {
  int i, len, x, y, dir; 

  dir = *origdir;
  x = *origx;
  y = *origy;

  len = strlen(str);
  i=0;

  //Iterate through each character
  while(i < len) {
    char c = str[i];

    switch(c) {
    case 'L': // Turn left
      switch(dir) {
      case N:
         x--;
         dir = W;
         break;
      case S:
         x++;
         dir = E;
         break;
      case E:
         y++;
         dir = N;
         break;
      case W:
         y--;
         dir = S;
         break;
      }
      break;

    case 'R': // Turn right
      switch(dir) {
      case N:
         x++;
         dir = E;
         break;
      case S:
         x--;
         dir = W;
         break;
      case E:
         y--;
         dir = S;
         break;
      case W:
         y++;
         dir = N;
         break;
      }
      break;

    case 'F': // Go forward
      switch(dir) {
      case N:
         y++;
         dir = N;
         break;
      case S:
         y--;
         dir = S;
         break;
      case E:
         x++;
         dir = E;
         break;
      case W:
         x--;
         dir = W;
         break;
      }
      break;
    }

    // Update max radius till now
    double rad = x*x + y*y;
    if(rad > *maxrad)
      *maxrad = rad;
    i++;
  }

  *origx = x;
  *origy = y;
  *origdir = dir;
}

// Function to compute the max radius of movement, if bounded
double findCircle(char *str) {
  int x=0, y=0, dir=N;
  int refx, refy;
  double radius = 0, maxrad = 0;

  // Starting from origin(x=0, y=0), find new pos after single iteration
  findNewPos(str, &dir, &x, &y, &maxrad);

  refx = x;
  refy = y;

  // Find new positions after 4 more iterations
  findNewPos(str, &dir, &x, &y, &maxrad);
  findNewPos(str, &dir, &x, &y, &maxrad);
  findNewPos(str, &dir, &x, &y, &maxrad);
  findNewPos(str, &dir, &x, &y, &maxrad);

  // Are we back to position where we were after 1st iteration?
  if(x == refx && y == refy) {
    printf("Circle exists %f!\n", maxrad);
    radius = sqrt(maxrad);
  }
  else {
    printf("Circle does not exist!\n");
    radius = -1;
  }

  return radius;
}

Answer 4

遍历给定的字符串一次并记下最终的位移和方向。如果位移不为零且单次迭代中机器人的起始方向和结束方向相同，则您的机器人不能包含在一个圆中，否则可以。

图：
在图中，假设机器人在给定字符串的单次迭代后从 A 点移动到 B 点。现在，角 ABC 是 (90 - theta)，这使得角 ABD 等于 90 度。所有边都相等且每个角都等于 90 度的四边形 ABDE 是正方形。对于任何 theta 值（锐角或钝角）都是如此。如果留下单次迭代后的结束方向，证明将是相似的。向南，机器人将在A点和B点之间摆动。

因此，作为您问题的解决方案，您可以在机器人完成给定字符串的一次迭代后，检查起点和终点方向是否相同以及起点和终点位置是否不同.

Answer 5

string doesCircleExists(string commands) {
    int dir=1; //1 is east; 2 north etc.
    pair<int,int> pos; 
    pos = make_pair(0,0);  //start at origin
    for(int i=0;i<4;i++) {
    for(int i=0;i<commands.size(); i++)
    {
       if(commands[i]=='F')
       {
        if(dir==1) pos.first++;  if(dir==2) pos.second++; 
        if(dir==3) pos.first--; if(dir==0) pos.second--; 
       }
       if(commands[i]=='L') {dir++; dir = dir%4;}
       if(commands[i]=='R') {dir--; dir = dir%4;}
    }
    }
    if(pos.first==0 && pos.second==0 && dir=1) return "YES"; else return "NO";

}

Answer 6

这可能有效：

def encircular(string):

    ini_pos = [0,0]
    position = [0,0]
    direction = 'N'
    directions = {'NL':'W','NR':'E','EL':'N','ER':'S','SL':'E','SR':'W','WL':'S','WR':'N'}
    forward = {'N':[0,1],'E':[1,0],'S':[0,-1],'W':[-1,0]}
    for i in range(4):
        for i in string:
            if i == 'F':
                position = [x+y for x,y in zip(position,forward[direction])]
            else:
                #print(direction+i)
                direction = directions[direction+i]
                #print (direction)
    if ini_pos == position: return 'YES'
    else : return 'NO'

Answer 7

def robot_bot(string):
    face = 0
    pos = [0, 0]
    string = string.upper()
    dirc = {
        0: [1, 0],
        90: [0, 1],
        180: [-1, 0],
        270: [0, -1],
        360: [1, 0],
        -90: [0, -1],
        -180: [-1, 0],
        -270: [0, 1]
    }
    for _ in range(4):
        for ch in string:
            if ch == "R": face -= 90
            elif ch == "L": face += 90
            if ch == "G":
                pos[0] += dirc[face][0]
                pos[1] += dirc[face][1]
            if abs(face) == 360:
                face = 0
    return True if pos == [0, 0] else False

Answer 8

#include <bits/stdc++.h>
using namespace std;
struct point
{
    int x;
    int y;
    int dir;
};
int mod4(int a)
{
    if(a%4 < 0)
        return (a%4 + 4);
    else
        return a%4;
}
int main()
{
    struct point p;
    p.x = 0;
    p.y = 0;
    p.dir = 0;
    string s;cin>>s;
    int j;
    for(int i=0;i<4*s.size();i++)
    {
        j = i%s.size();
        if(s[j] == 'F')
        {
            if(p.dir == 0)//north
                p.y++;
            if(p.dir == 1)//east
                p.x++;
            if(p.dir == 2)//south
                p.y--;
            if(p.dir == 3)//west
                p.x--;
        }
        if(s[j] == 'L')
        {
            p.dir--;
            p.dir = mod4(p.dir);
        }
        if(s[j] == 'R')
        {
            p.dir++;
            p.dir = mod4(p.dir);
        }
        //cout<<p.x<<" "<<p.y<<" "<<p.dir<<endl;
    }
    if(p.x == 0 && p.y ==0 && p.dir == 0)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;   
}

检查是否存在圆

Check If there exists a Circle

algorithm

geometry

computational-geometry