【HackerRank】Coin on the Table

一开始想用DFS做的，做了好久都超时。

看了题解才明白要用动态规划。

设置一个三维数组dp，其中dp[i][j][k]表示在时间k到达(i,j)所需要做的最小改动，那么递推式如下：

图片来源：Editorial，其中当从周围的格子可以直接移动到(i,j)时，delta=0；否则，需要改变周围格子的方向符号，delta=1。

即k-1时刻在(i,.j)周围的四个格子，然后在k时刻移动到(i,j)。并且，看这四个格子中的方向符号是否直接可以完成这次移动，否则就改变这四个格子的方向符号。

代码如下：

 import java.util.*;

 public class Solution {    

     public static void main(String[] args) {

         Scanner in = new Scanner(System.in);

         int n = in.nextInt();

         int m = in.nextInt();

         int K = in.nextInt();

         char[][] map= new char[n][m];

         int[][][] dp = new int[n][m][K+1];

         int star_x = 0;

         int star_y = 0;

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

             String s = in.next();

             if(s.contains("*"))

             {

                 star_x = i;

                 star_y = s.indexOf("*");

             }

             map[i]=s.toCharArray();

         }

         for(int k=0;k <= K;k++){

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

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

                     if(k==0)

                         dp[i][j][k] = (i==0&&j==0? 0:Integer.MAX_VALUE-1);

                     else{

                         dp[i][j][k] = CalcuMin(i,j,k,dp,map);

                     }

                 }

             }

         }

         int answer = Integer.MAX_VALUE-1;

         for(int k = 0;k <= K;k++){

             answer = Math.min(answer, dp[star_x][star_y][k]);

         }

         System.out.println(answer==Integer.MAX_VALUE-1?-1:answer);

     }

     private static int CalcuMin(int i, int j, int k,int[][][] dp, char[][] map) {

         // TODO Auto-generated method stub

         int mini = Integer.MAX_VALUE-1;

         int n = map.length;

         int m = map[0].length;

         if(i-1>=0){

             if(dp[i-1][j][k-1]+(map[i-1][j]=='D'?0:1) < mini )

                 mini = Math.min(mini,dp[i-1][j][k-1]+(map[i-1][j]=='D'?0:1));

         }

         if(i+1<n){

             if(dp[i+1][j][k-1]+(map[i+1][j]=='U'?0:1) < mini )

                 mini = Math.min(mini,dp[i+1][j][k-1]+(map[i+1][j]=='U'?0:1));

         }

         if(j-1>=0){

             if(dp[i][j-1][k-1]+(map[i][j-1]=='R'?0:1) < mini )

                 mini = Math.min(mini,dp[i][j-1][k-1]+(map[i][j-1]=='R'?0:1));

         }

         if(j+1<m){

             if(dp[i][j+1][k-1]+(map[i][j+1]=='L'?0:1) < mini )

                 mini = Math.min(mini,dp[i][j+1][k-1]+(map[i][j+1]=='L'?0:1));

         }

         return mini;

     }

 }

巴特西

【HackerRank】Coin on the Table

最新文章

热门文章