Robot

Code

public class Robot {

    static int[] dx = {-1,  0,  1,-1, 1, -1, 0, 1 };

    static int[] dy = {-1, -1, -1, 0, 0,  1, 1, 1 };

    public int getProb(String[] floor, int x, int y, int time) {

        int rx = 0;

        int ry = 0;

        for (int cx=0; cx<floor[0].length(); cx++) {

            for (int cy=0; cy<floor.length; cy++) {

                if (floor[cy].charAt(cx)=='R') {

                    rx=cx;

                    ry=cy;

                }

            }

        }

        int sx = floor[0].length();

        int sy = floor.length;

        double[][] cp = new double[sx][sy];

        cp[rx][ry]=1;

        for (int t=0; t<time; t++) {

            double[][] np = new double[sx][sy];

            for (int cx=0; cx<sx; cx++) {

                for (int cy=0; cy<sy; cy++) {

                    int nmoves=0;

                    for (int d=0; d<8; d++) {

                        int nx = cx+dx[d];

                        int ny = cy+dy[d];

                        if (nx<0 || nx>=sx) continue;

                        if (ny<0 || ny>=sy) continue;

                        if (floor[ny].charAt(nx)=='X') continue;

                        if (floor[cy].charAt(nx)=='X' || floor[ny].charAt(cx)=='X') continue;

                        np[nx][ny]+=cp[cx][cy]/8;

                        nmoves++;

                    }

                    np[cx][cy]+=(cp[cx][cy]*(8-nmoves))/8;

                }

            }

            cp=np;

        }

        return (int)(cp[x][y]*1000);

    }

}

Explanation

핵심은 "해당 위치에 도달하는 성공 확률"이 아닌 "12.5%로 움직이는 확률"을 저장한다는 것이다. 이동 방향이 있으면 그 자리(nx,ny)에 1/8을 더하고, 없으면 8 - (부동 방향)을 해당 자리(cx, cy)에 더한다. 모든 확률을 저장하므로 결과값은 정확하다.

References

https://community.topcoder.com/stat?c=problem_solution&cr=114853&rd=4497&pm=1583