9.18 商汤科技笔试

Myth丶恋晨 2022-12-08 06:32 138阅读 0赞

# 1. 第一题：走迷宫 门 ABCDE 锁abcde 墙X .路 #

// AC: 60%
    
    import java.util.*;
    
    public class Main1 { 
    
        public static void dfs(char map[][], int i, int j)
        { 
            if(i < 0 || i >= map.length || j < 0 || j >= map[0].length || map[i][j] == 'X' || map[i][j] == '*')
            { 
                return;
            }
            map[i][j] = '*';
            dfs(map, i + 1, j);
            dfs(map, i - 1, j);
            dfs(map, i, j + 1);
            dfs(map, i, j - 1);
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt())
            { 
                int n = sc.nextInt();
                int m = sc.nextInt();
                if(n == 0 && m == 0)
                { 
                    return;
                }
                char map[][]  = new char[n][m];
                int start_x = -1;
                int start_y = -1;
                int end_x = -1;
                int end_y = -1;
                for(int i = 0; i < n; i++)
                { 
                    String temp = sc.next();
                    for(int j = 0; j < m; j++)
                    { 
                        map[i][j] = temp.charAt(j);
                        if(map[i][j] == 'S')
                        { 
                            start_x = i;
                            start_y = j;
                        }
                        if(map[i][j] == 'G')
                        { 
                            end_x = i;
                            end_y = j;
                        }
                    }
                }
                dfs(map, start_x, start_y);
                if(map[end_x][end_y] == '*')
                { 
                    System.out.println("YES");
                }
                else
                { 
                    System.out.println("NO");
                }
            }
        }
    }
    
    
    // 输入:
    //7 20
    //......G..X...dX.X...
    //.b.......bXX.X..Xb.D
    //dX.X.....X.aXe..c...
    //X...D..XX..X..D....c
    //a..X.Xc.c..bXDXac...
    //.......C..X.X.c...Xb
    //b.....eXA..SA..X.dX.
    //
    //15 11
    //Xd...E.XaE.
    //D.E..X..DXB
    //..A.E...DBb
    //DX.X..DX.ED
    //..XX.DXAc..
    //..XE.X..X.X
    //c...B...X.B
    //.X.DX..Xa.b
    //GcXE.B....B
    //..A..A..Xea
    //BX.EdEa..ab
    //e..XSE.B...
    //.XA...X.X.C
    //Cc.X..XeBcb
    //CXXCC...bX.
    //
    //0 0
    
    // 输出:
    // YES
    //
    // NO

# 2. 第二题：某点到 多边形 每条边的最短距离 #

// AC: 100%
    
    // 基本原理是逐条边判断与待检测点的距离
    import java.util.*;
    
    // 工具类
    public class Main2 { 
    
        // 实体类
        public static class Point
        { 
            double x; // x轴坐标
            double y; // y轴坐标
    
            public Point setPoint(Point point)
            { 
                this.x = point.getX();
                this.y = point.getY();
                return this;
            }
    
            public Point()
            { 
    
            }
    
            public Point(Float[] point)
            { 
                this.x = point[0];
                this.y = point[1];
            }
    
            public Point(Double[] point)
            { 
                this.x = point[0];
                this.y = point[1];
            }
    
            public Point(double x, double y)
            { 
                this.x = x;
                this.y = y;
            }
    
            public double getX()
            { 
                return x;
            }
    
            public void setX(double x)
            { 
                this.x = x;
            }
    
            public double getY()
            { 
                return y;
            }
    
            public void setY(double y)
            { 
                this.y = y;
            }
        }
    
    
        /** * 获取点与直线之间的距离 * @param p 点 * @param a 直线上一点 * @param b 直线上一点 * @return */
        public static double pointToLineDist(Point p, Point a, Point b)
        { 
            double ABx = b.x - a.x;
            double ABy = b.y - a.y;
            double APx = p.x - a.x;
            double APy = p.y - a.y;
    
            double AB_AP = ABx * APx + ABy * APy;
            double distAB2 = ABx * ABx + ABy * ABy;
    
            double Dx = a.x, Dy = a.y;
    
            if(distAB2 != 0)
            { 
                double t = AB_AP / distAB2;
                if(t >= 1)
                { 
                    Dx = b.x;
                    Dy = b.y;
                }
                else if(t > 0)
                { 
                    Dx = a.x + ABx * t;
                    Dy = a.y + ABy * t;
                }
                else
                { 
                    Dx = a.x;
                    Dy = a.y;
                }
            }
    
            double PDx = Dx - p.x, PDy = Dy - p.y;
            return Math.sqrt(PDx * PDx + PDy * PDy);
        }
    
        /** * 获取点与多边形之间最近距离 * @param point * @param points * @return 0.0 ：点位于多边形内部 >0.0 : 点与多边形之间的最近距离 */
        public static double pintoToPolygonMinDist(Point point, List<Point> points)
        { 
            double dist = Double.MAX_VALUE;
            int N = points.size();
            for(int i = 0, j = N - 1; i < N; j = i++)
            { 
                dist = Math.min(dist, pointToLineDist(point, points.get(i), points.get(j)));
            }
            return dist;
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
    
            Double Ax = sc.nextDouble();
            Double Ay = sc.nextDouble();
    
            Point p = new Point();
            p.x = Ax;
            p.y = Ay;
    
            int n = sc.nextInt();
    
            List<Point> list = new ArrayList<>();
    
            for(int i = 0; i < n; i++)
            { 
                Point point = new Point();
                point.x = sc.nextDouble();
                point.y = sc.nextDouble();
                list.add(point);
            }
    
            double res = pintoToPolygonMinDist(p, list);
            // %.3f 其中: %. 表示 小数点前任意位数，3 表示 三位小数，格式后的结果为f 表示 浮点型
            System.out.printf("%.3f", res);
        }
    }
    
    // 输入:
    //794.478 -175.513
    //10
    //202.27 -963.723
    //476.254 -887.972
    //833.666 -514.638
    //959.625 142.19
    //936.967 987.264
    //-481.222 990.566
    //-846.523 924.932
    //-968.741 -147.723
    //-731.881 -755.811
    //-175.924 -891.911
    
    // 输出:
    //102.356

# 3. 参考： #

1.  [商汤笔试-开发大类B卷编程题投票][-_B]
2.  [商汤科技9.16 数据开发笔试(B卷)][9.16 _B]
3.  [商汤第一题代码][Link 1]
4.  [判断点与多边形的最小距离][Link 2]
5.  [商汤科技2020-8-20开发笔试A卷][2020-8-20_A]

[-_B]: https://www.nowcoder.com/discuss/516418
[9.16 _B]: https://www.nowcoder.com/discuss/516416
[Link 1]: https://www.nowcoder.com/discuss/516463
[Link 2]: https://blog.csdn.net/aaronmer/article/details/103684112
[2020-8-20_A]: https://www.nowcoder.com/discuss/483879