fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11. 	static int n,m;
  12. 	static boolean lock[][];
  13. 	static int map[][];
  14.  
  15. 	public static void main (String[] args) throws java.lang.Exception
  16. 	{
  17. 		int map[][] = {{0,1,0,0,0,1,0,0},{0,1,0,1,0,1,0,0},{0,0,0,1,0,0,0,0},{1,1,1,1,1,1,1,0},{1,1,1,1,1,1,1,0},{1,1,1,1,1,1,1,0},{1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,0}};
  18.  
  19. 		/*{{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  20. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  21. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  22. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  23. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  24. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  25. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  26. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  27. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  28. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  29. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  30. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  31. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  32. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  33. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  34. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  35. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  36. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  37. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  38. 		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};*/
  39. 	//{{0,1,1,1,1,0,0,0},{0,0,0,0,0,1,1,0}};
  40. 	//{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}};
  41. 	//{{0,1,0,0,0,1,0,0},{0,1,0,1,0,1,0,0},{0,0,0,1,0,0,0,0},{1,1,1,1,1,1,1,0},{1,1,1,1,1,1,1,0},{1,1,1,1,1,1,1,0},{1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,0}};
  42. 	//{{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 0}};
  43. 	//{{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}};
  44.  
  45. 	System.out.println(solution(map));
  46. 	}
  47.  
  48.  
  49. 	 public static int solution(int[][] map) {
  50.  
  51. 	 	n = map.length;
  52.         m = map[0].length;
  53.         lock = new boolean[n][m];
  54.         Ideone.map = map;
  55.  
  56.         return findPath(0,0,0,false);
  57.  
  58.  
  59. 	 }
  60.  
  61. 	 public static int findPath(int x,int y,int length,boolean barrierRemoved){
  62.  
  63. 	 	if(x==n-1&&y==m-1)
  64. 	 	return length+1;
  65.  
  66. 	 	if(!(x>=0&&x<n&&y>=0&&y<m))
  67. 	 	return Integer.MAX_VALUE;
  68.  
  69. 	 	//System.out.println(x+","+y);
  70.  
  71. 	 	if(lock[x][y])
  72. 	 	return Integer.MAX_VALUE;
  73.  
  74. 	 	if(map[x][y]==1&&barrierRemoved)
  75. 	 	return Integer.MAX_VALUE;
  76.  
  77. 	 	lock[x][y] = true;
  78. 	 	if(map[x][y]==1)
  79. 	 	barrierRemoved = true;
  80.  
  81.  
  82.  
  83. 	 	int northPathLength = findPath(x+1,y,length+1,barrierRemoved);
  84.  
  85. 	 	int southPathLength = findPath(x-1,y,length+1,barrierRemoved);
  86.  
  87. 	 	int eastPathLength = findPath(x,y+1,length+1,barrierRemoved);
  88.  
  89. 	 	int westPathLength = findPath(x,y-1,length+1,barrierRemoved);
  90.  
  91. 		lock[x][y] = false;
  92.  
  93. 	 	return Math.min(northPathLength,Math.min(southPathLength,Math.min(eastPathLength,westPathLength)));
  94.  
  95. 	 }
  96.  
  97. }
Success #stdin #stdout 0.06s 32452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
19
https://ideone.com/Kuj9Yu
language:
Java (HotSpot 12)
created:
4 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!