CodinGame - A child's play 思路

秒速五厘米 2023-07-10 05:27 18阅读 0赞

题目来源：[CodinGame A child’s play][CodinGame A child_s play]

## 要求 ##

机器人在规定区域内行走，初始向上，遇到障碍物右转，有行走步数规定，输出最后停留位置

*  出界检查（可不必）
 *  节省时间

## 思路 ##

通过记录路线，再进行比对就可知道循环一圈的步数，然后根据剩余步数可以直接得出停止位置

## 代码 ##

import java.util.*;
    
    class Solution { 
    
       public static void main(String args[]) { 
            Scanner in = new Scanner(System.in);
            int w = in.nextInt();
            int h = in.nextInt();
            long n = in.nextLong();
            int angle = -270;//初始向上角度
            List<String> map = new ArrayList<>();
            List<Point> history = new ArrayList<>();
            List<Point> check_history = new ArrayList<>();
            boolean repeat = false;
            Point p = new Point(-1,-1);
            System.err.println(w);//
            System.err.println(h);//
            System.err.println(n);//
            if (in.hasNextLine()) { 
                in.nextLine();
            }
            for (int i = 0; i < h; i++) { 
                String line = in.nextLine();
                map.add(line);
                System.err.println(line);//
                if (p.x == -1 && line.contains("O")){ 
                    p.x = line.indexOf("O");
                    p.y=i;
                }
            }
            System.err.println(p);//
            while (n>0){ 
                //路径重复判断
                if ( history.size()>4&& history.size() != check_history.size() && p.equals(history.get(check_history.size()))){ 
                    repeat = true;
                    System.err.println("Repeat");//
                }
                else { 
                    if (repeat && history.size() == check_history.size()){ //出现完全重复路径
                        System.err.println("EndOfRepeat");//
                        n %= check_history.size();
                        p = history.get((int)n);
                        break;
                    }
                    repeat = false;
                }
                if (repeat){ 
                    check_history.add(new Point(p.x,p.y));
                }
                else { 
                    if (check_history.size()>0){ 
                        history.addAll(check_history);
                        check_history.clear();
                    }
                    history.add(new Point(p.x,p.y));
                }
                //出界&转向
                if (angle == 0){ //Right
                    if (p.x == w-1){ 
                        break;
                    }
                    if (map.get(p.y).charAt(p.x+1) == '#'){ 
                        angle -= 90;
                    }
                }
                else if (angle == -90){ //Down
                    if (p.y == h-1){ 
                        break;
                    }
                    if (map.get(p.y+1).charAt(p.x) == '#'){ 
                        angle -= 90;
                    }
                }
                else if (angle == -180){ //Left
                    if (p.x == 0){ 
                        break;
                    }
                    if (map.get(p.y).charAt(p.x-1) == '#'){ 
                        angle -= 90;
                    }
                }
                else if (angle == -270){ //Top
                    if (p.y == 0){ 
                        break;
                    }
                    if (map.get(p.y-1).charAt(p.x) == '#'){ 
                        angle -= 90;
                    }
                }
                //角度处理
                if (angle == -360){ 
                    angle =0;
                }
                //移动
                if (angle == 0){ 
                    p.x++;
                }
                else if (angle == -90){ 
                    p.y++;
                }
                else if (angle == -180){ 
                    p.x--;
                }
                else if (angle == -270){ 
                    p.y--;
                }
                System.err.println(p.x+" "+p.y);//
                n--;
            }
            System.out.println(p.x+" "+p.y);
        }
    }
    class Point{ 
        int x,y;
    
        public Point(int x, int y) { 
            this.x = x;
            this.y = y;
        }
    
        @Override
        public boolean equals(Object obj) { 
            if (obj instanceof Point){ 
    
                Point p = (Point)obj;
                System.err.println(obj == this);//
                return p.x == this.x && p.y == this.y;
            }
            return false;
        }
    
        @Override
        public String toString() { 
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }

[CodinGame A child_s play]: https://www.codingame.com/ide/puzzle/a-childs-play