首页 > 代码库 > 【HackerRank】Coin on the Table

【HackerRank】Coin on the Table

2024-07-18 04:33:53   214人阅读

题目链接：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)。并且，看这四个格子中的方向符号是否直接可以完成这次移动，否则就改变这四个格子的方向符号。

代码如下：

 1 import java.util.*; 2  3 public class Solution {     4      5     public static void main(String[] args) { 6         Scanner in = new Scanner(System.in); 7         int n = in.nextInt(); 8         int m = in.nextInt(); 9         int K = in.nextInt();10         11         char[][] map= new char[n][m];12         int[][][] dp = new int[n][m][K+1];13         14         int star_x = 0;15         int star_y = 0;16         17         for(int i = 0;i < n;i++){18             String s = in.next();19             if(s.contains("*"))20             {21                 star_x = i;22                 star_y = s.indexOf("*");23             }24             map[i]=s.toCharArray();25         }26         27         for(int k=0;k <= K;k++){ 28             for(int i = 0;i < n;i++){29                 for(int j = 0;j < m;j++){30                     if(k==0)31                         dp[i][j][k] = (i==0&&j==0? 0:Integer.MAX_VALUE-1);32                     else{33                         dp[i][j][k] = CalcuMin(i,j,k,dp,map);34                     }35                 }36             }37         }38         39         int answer = Integer.MAX_VALUE-1;40         for(int k = 0;k <= K;k++){41             answer = Math.min(answer, dp[star_x][star_y][k]);42         }43         44         System.out.println(answer==Integer.MAX_VALUE-1?-1:answer);45         46     }47 48     private static int CalcuMin(int i, int j, int k,int[][][] dp, char[][] map) {49         // TODO Auto-generated method stub50         int mini = Integer.MAX_VALUE-1;51         int n = map.length;52         int m = map[0].length;53         54         if(i-1>=0){55             if(dp[i-1][j][k-1]+(map[i-1][j]==‘D‘?0:1) < mini )56                 mini = Math.min(mini,dp[i-1][j][k-1]+(map[i-1][j]==‘D‘?0:1));57         }58         59         if(i+1<n){60             if(dp[i+1][j][k-1]+(map[i+1][j]==‘U‘?0:1) < mini )61                 mini = Math.min(mini,dp[i+1][j][k-1]+(map[i+1][j]==‘U‘?0:1));62         }63         64         if(j-1>=0){65             if(dp[i][j-1][k-1]+(map[i][j-1]==‘R‘?0:1) < mini )66                 mini = Math.min(mini,dp[i][j-1][k-1]+(map[i][j-1]==‘R‘?0:1));67         }68         69         if(j+1<m){70             if(dp[i][j+1][k-1]+(map[i][j+1]==‘L‘?0:1) < mini )71                 mini = Math.min(mini,dp[i][j+1][k-1]+(map[i][j+1]==‘L‘?0:1));72         }73         return mini;74     }75 }

 


联系
我们