fork(7) download
copy 
  1. public class Main {
  2. 	private static int n;
  3. 	private static int m;
  4. 	private static int [][]grid;
  5. 	private static int [][]q;
  6.  
  7. 	public static void main(String[] args) throws Exception{
  8. 		java.io.BufferedReader in = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
  9.  
  10. 		String[] f = in.readLine().split(" ");
  11.     	n = Integer.parseInt(f[0]);
  12.     	m = Integer.parseInt(f[1]);
  13.     	if (n > 0 && m > 0) {
  14. 	    	grid = new int[n][m];
  15. 		q = new int[n][m];
  16.  
  17. 	    	for (int i=0; i<n; i++) {
  18. 	    		String[] s = in.readLine().split(" ");
  19. 	    		for (int j=0;j<s.length;j++) {
  20. 	    			grid[i][j] = Integer.parseInt(s[j]);
  21. 				q[i][j] = grid[i][j];
  22. 	    		}
  23. 	    	}
  24.     	}
  25.     	System.out.println(n>0&&m>0?computeShortest():"0");
  26. 	}
  27.  
  28. 	private static void computeShortestPathArrays() {
  29. 		for (int y=n-1;y>=0;y--) {
  30. 			for (int x=0;x<m;x++) {
  31. 				if (y==n-1) {
  32. 					q[y][x] = grid[y][x];
  33. 				}else {
  34. 					int m = getMin(y,x);
  35. 					q[y][x] = m + grid[y][x];
  36. 				}
  37. 			}
  38. 		}
  39. 	}
  40.  
  41. 	private static int computeShortest() {
  42. 		computeShortestPathArrays();
  43. 		java.util.Arrays.sort(q[0]);
  44. 		return q[0][0];
  45. 	}
  46.  
  47. 	private static int getMin(int y, int x) {
  48. 		if (y==n-2) {
  49. 			if (x==0) {
  50. 				return Math.min(grid[y+1][x], grid[y+1][x+1]);
  51. 			}else if (x==m-1) {
  52. 				return Math.min(grid[y+1][x-1], grid[y+1][x]);
  53. 			}else {
  54. 				return Math.min(grid[y+1][x-1], Math.min(grid[y+1][x], grid[y+1][x+1]));
  55. 			}
  56. 		}else {
  57. 			if (x==0) {
  58. 				return Math.min(q[y+1][x], q[y+1][x+1]);
  59. 			}else if (x==m-1) {
  60. 				return Math.min(q[y+1][x-1], q[y+1][x]);
  61. 			}else {
  62. 				return Math.min(q[y+1][x-1], Math.min(q[y+1][x], q[y+1][x+1]));
  63. 			}
  64. 		}
  65. 	}
  66. }
Success #stdin #stdout 0.03s 245632KB
comments (?)
stdin
copy 
4 3 
5 6 1 
3 5 7 
3 4 6 
2 4 6
stdout
copy 
11
https://ideone.com/RAVt4
language:
Java (HotSpot 12)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!