WaterPressure Topcoder



import java.util.ArrayList;


public class WaterPressure
{
    int[] dy = {-1,0,1,0};
    int[] dx = {0,1,0,-1};

    class Point {
        int x,y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int howLong(String[] layout) {
        int r = layout.length;
        int c = layout[0].length();

        boolean[][] reached = new boolean[r][c];

        int[][] l = new int[r][c];
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                l[i][j] = layout[i].charAt(j)-'0';

        ArrayList<Point> a = new ArrayList<Point>();
        a.add(new Point(0,0));

        double amount = 2;
        double squares = 0;
        double pressure = amount/1;

        int sec = 0;
        while (true) {
            int len = a.size();
            for (int i = 0; i < len; i++) {
                Point p = a.get(i);
                if(pressure > l[p.y][p.x]) {
                    l[p.y][p.x] = 40;

                    for (int j = 0; j < 4; j++) {
                        int y = p.y + dy[j];
                        int x = p.x + dx[j];
                        if(y>=0 && x>=0 && y<r && x<c && l[y][x]!=40 && !reached[y][x]) {    // 40 is equal to 'X'
                            reached[y][x] = true;
                            a.add(new Point(x,y));
                        }
                    }

                    squares++;
                    a.remove(i--); len--;
                }
            }

            if (a.size() == 0) {sec--; break;}

            pressure = amount/squares;

            sec++; amount++;
        }

        // checking map
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                if(l[i][j] != 40) return -1;

        return sec;
    }
}


Explanation

reached[][]    ArrayList에 물이 넘치는지 아닌지 확인해야 하는 배열

  • 'X' - '0'을 하게 되면 정수값으로 40이 나온다. 이 값을 물이 도달할 수 없는 값으로 사용했다.
  • 수압이 현재 칸보다 높을 경우 해당 칸의 상하좌우를 확인하고 나서 정상적인 칸을 집어넣는다.
  • checking map은 물이 도달하지 못한 칸을 조사한다.


1 2 3 4 5 6 7 8 9 10 다음