공 이동 시뮬레이션

격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는 2차원 정수 배열 queries가 매개변수로 주어집니다. n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ n ≤ 109
1 ≤ m ≤ 109
0 ≤ x < n
0 ≤ y < m
1 ≤ queries의 행의 개수 ≤ 200,000
queries의 각 행은 [command,dx] 두 정수로 이루어져 있습니다.
0 ≤ command ≤ 3
1 ≤ dx ≤ 109
이는 query(command, dx)를 의미합니다.

문제풀이

1. DFS,BFS로 풀기에는 범위가 너무 넓기때문에 가능해보이지가 않는다.
2. 그렇다면 끝에서 시작으로 푸는 역순방식으로 푸는게 맞아보인다.
3. 역순으로 풀이된다면 범위와 넘어가는 조건 그리고 결과값을 어떻게 구해야하는가?

• 만약 범위가 아예 넘어간다면 가능한 케이스가 없으므로 종료해야한다.
• 만약 시작범위만 벗어난다면 시작범위만 0으로 초기화
• 만약 끝범위만 벗어난다면 끝범위만 최대 넓이로 초기화
• 아니라면 정상값 리턴.

코드

class Solution {
    int[] dy = new int[]{1,-1,0,0};
    int[] dx = new int[]{0,0,1,-1};
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long answer = -1;
        int sx,sy,ex,ey;
        sx = ex = x;
        sy = ey = y;
        for(int i=queries.length-1;i>=0;i--){
            //y열의 증가 감소
            if(queries[i][0]==1||queries[i][0]==0){
               int[] tmp = nextquery(m,queries[i][1]*dy[queries[i][0]],sy,ey);
               if(tmp[0]==-1) return 0;
                sy = tmp[0];
                ey = tmp[1];
            }else{//x행의 증가 감소                 
                int[] tmp = nextquery(n,queries[i][1]*dx[queries[i][0]],sx,ex);               
                if(tmp[0]==-1) return 0;
                sx = tmp[0];
                ex = tmp[1];
            }
        }
        
        return (long)(ex-sx+1) * (long)(ey-sy+1);
    }
   
       
    int[] nextquery(int m,int dir,int start,int end){
        int nexts = (start==0&& dir>0) ? 0 : start + dir;
        int nexte = (end==m-1&& dir<0) ? m-1 : end + dir;
        if((nexts < 0 || nexts >= m ) && (nexte < 0 || nexte > m)){
            return new int[]{-1,-1};
        }else if(nexts < 0 && nexte >= 0 && nexte < m) {
            return new int[]{0, nexte};
        }else if (nexte >= m && nexts >= 0 && nexts < m) {
            return new int[]{nexts, m-1};
        }
        return new int[]{nexts, nexte};     
    }
}// DFS BFS로 풀기에는 범위가 너무 넓음
//역순으로 풀어야겠다.
// 역순으로 값을 늘려가면서 풀면 마지막 증가값을 곱하면 최대값이 나온다.