阿祁的部落格

LeetCode 778 - Swim in Rising Water 解題心得( 題目 )

解題概念:Dijkstra's algorithm

解題方法:這題是個圖論題，雖然這題並不是正規的Dijkstra，但是可以使用其中pq的技巧，我們把目前拜訪過的格子的鄰居(這裡指的是還沒去過的)加入依高低排序的Priority Queue，之後取最小的出來，直到取到終點，答案就是所有從pq取出過最大的那個。

另外發現這題好像也可以二分搜水位高度做log(n^2)DFS，或是使用並查集，所以其實解法不只一種。

Java參考程式碼:

class Solution {

    boolean[][] vis=new boolean[55][55];

    int ans,n;

    public int swimInWater(int[][] grid) {

        n=grid.length;

        P p;

        PriorityQueue<P> pq=new PriorityQueue<>(new Comparator<P>() {

            public int compare(P f,P s) {

                return f.w-s.w;

            }

        });

        pq.clear();

        pq.offer(new P(0,0,grid[0][0]));

        while(!pq.isEmpty()) {

            p=pq.poll();

            ans=Math.max(ans,grid[p.x][p.y]);

            if(p.x==n-1&&p.y==n-1)return ans;

            if(p.x!=0&&!vis[p.x-1][p.y]) {

                pq.offer(new P(p.x-1,p.y,grid[p.x-1][p.y]));

                vis[p.x-1][p.y]=true;

            }

            if(p.y!=0&&!vis[p.x][p.y-1]) {

                pq.offer(new P(p.x,p.y-1,grid[p.x][p.y-1]));

                vis[p.x][p.y-1]=true;

            }

            if(p.x!=n-1&&!vis[p.x+1][p.y]) {

                pq.offer(new P(p.x+1,p.y,grid[p.x+1][p.y]));

                vis[p.x+1][p.y]=true;

            }

            if(p.y!=n-1&&!vis[p.x][p.y+1]) {

                pq.offer(new P(p.x,p.y+1,grid[p.x][p.y+1]));

                vis[p.x][p.y+1]=true;

            }

        }

        return -1;//never reach here 

    }

    

    public void init() {

        ans=0;

        for(int i=0;i<55;i++) {

            for(int j=0;j<55;j++) {

                vis[i][j]=false;

            }

        }

    }

}



class P{

    int x,y,w;

    P(int a,int b,int c){

        x=a;

        y=b;

        w=c;

    }

}