fork(1) download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. /*
  4. 원숭이 무빙으로 가던 와중 앞에 장애물이 나타났을 때,
  5. 말 무빙을 치면 최소거리지 않을까
  6. */
  7.  
  8. public class Main
  9. {
  10. 	static class node implements Comparable<node>
  11. 	{
  12. 		int r;
  13. 		int c;
  14. 		int k;
  15. 		int time;
  16.  
  17. 		public node(int r , int c , int k , int time)
  18. 		{
  19. 			this.r = r;
  20. 			this.c = c;
  21. 			this.k = k;
  22. 			this.time = time;
  23. 		}
  24.  
  25. 		public int compareTo(node n)
  26. 		{
  27. 			return time - n.time;
  28. 		}
  29. 	}
  30. 	static int k , r , c , ans;
  31. 	static int[][] map;
  32. 	static boolean[][] visit;
  33. 	static int[] mr = {-1,0,1,0};
  34. 	static int[] mc = {0,1,0,-1};
  35. 	static int[] hr = {-2,-2,-1,1,2,2,1,-1};
  36. 	static int[] hc = {-1,1,2,2,1,-1,-2,-2};
  37. 	static PriorityQueue<node> pq;
  38.  
  39. 	public static void main (String[] args) throws IOException
  40. 	{
  41. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  42. 		k = Integer.parseInt(br.readLine());
  43.  
  44. 		StringTokenizer st = new StringTokenizer(br.readLine());
  45. 		c = Integer.parseInt(st.nextToken());
  46. 		r = Integer.parseInt(st.nextToken());
  47. 		map = new int[r][c];
  48. 		visit = new boolean[r][c];
  49. 		pq = new PriorityQueue<>();
  50.  
  51. 		for(int i = 0 ; i < r ; i++)
  52. 		{
  53. 			st = new StringTokenizer(br.readLine());
  54. 			for(int j = 0 ; j < c ; j++)
  55. 			{
  56. 				map[i][j] = Integer.parseInt(st.nextToken());
  57. 			}
  58. 		}
  59.  
  60. 		visit[0][0] = true;
  61. 		pq.add(new node(0,0,k,0));
  62.  
  63. 		bfs();
  64. 		System.out.println(ans);
  65. 	}
  66. 	public static void bfs()
  67. 	{
  68. 		while(!pq.isEmpty())
  69. 		{
  70. 			node nod = pq.poll();
  71. 			System.out.println(nod.r+","+nod.c+" // "+nod.time);
  72.  
  73.  
  74. 			if(nod.r == r-1 && nod.c == c-1)
  75. 			{
  76. 				ans = nod.time;
  77. 				return;
  78. 			}
  79.  
  80. 			for(int i = 0 ; i < 4 ; i++)
  81. 			{
  82. 				int nr = nod.r + mr[i];
  83. 				int nc = nod.c + mc[i];
  84.  
  85. 				if(nr >= 0 && nc >= 0 && nr < r && nc < c)
  86. 				{
  87. 					if(nod.k > 0 /*&& map[nr][nc] == 1*/)
  88. 					{
  89. 						horse_moving(nod.r,nod.c,nod.k,nod.time);
  90. 					}
  91. 					if(map[nr][nc] == 0 && !visit[nr][nc])
  92. 					{
  93. 						visit[nr][nc] = true;
  94. 						pq.add(new node(nr,nc,nod.k,nod.time+1));
  95. 					}
  96. 				}
  97. 			}
  98. 		}
  99.  
  100. 		ans = -1;
  101. 	}
  102. 	public static void horse_moving(int r , int c , int k , int time)
  103. 	{
  104. 		System.out.println("뛰어넘으려는 시도: "+r+","+c);
  105. 		for(int i = 0 ; i < 8 ; i++)
  106. 		{
  107. 			int nr = r + hr[i];
  108. 			int nc = c + hc[i];
  109.  
  110. 			if(nr >= 0 && nc >= 0 && nr < r && nc < c)
  111. 			{
  112. 				System.out.println("뛰어넘기 검사중...: "+nr+","+nc+" // "+map[nr][nc]);
  113. 				if(!visit[nr][nc] && map[nr][nc] == 0)
  114. 				{
  115. 					System.out.println("뛰어넘은 결과: "+nr+","+nc);
  116. 					visit[nr][nc] = true;
  117. 					pq.add(new node(nr,nc,k-1,time+1));
  118. 				}
  119.  
  120. 			}
  121. 		}
  122. 	}
  123. }
Success #stdin #stdout 0.22s 53436KB
comments (?)
stdin
copy 
1
4 4
0 0 0 0
1 0 0 0
0 0 1 0
0 1 0 0
stdout
copy 
0,0 // 0
뛰어넘으려는 시도: 0,0
뛰어넘으려는 시도: 0,0
0,1 // 1
뛰어넘으려는 시도: 0,1
뛰어넘으려는 시도: 0,1
뛰어넘으려는 시도: 0,1
0,2 // 2
뛰어넘으려는 시도: 0,2
뛰어넘으려는 시도: 0,2
뛰어넘으려는 시도: 0,2
1,1 // 2
뛰어넘으려는 시도: 1,1
뛰어넘으려는 시도: 1,1
뛰어넘으려는 시도: 1,1
뛰어넘으려는 시도: 1,1
1,2 // 3
뛰어넘으려는 시도: 1,2
뛰어넘기 검사중...: 0,0 // 0
뛰어넘으려는 시도: 1,2
뛰어넘기 검사중...: 0,0 // 0
뛰어넘으려는 시도: 1,2
뛰어넘기 검사중...: 0,0 // 0
뛰어넘으려는 시도: 1,2
뛰어넘기 검사중...: 0,0 // 0
2,1 // 3
뛰어넘으려는 시도: 2,1
뛰어넘기 검사중...: 0,0 // 0
뛰어넘으려는 시도: 2,1
뛰어넘기 검사중...: 0,0 // 0
뛰어넘으려는 시도: 2,1
뛰어넘기 검사중...: 0,0 // 0
뛰어넘으려는 시도: 2,1
뛰어넘기 검사중...: 0,0 // 0
0,3 // 3
뛰어넘으려는 시도: 0,3
뛰어넘으려는 시도: 0,3
2,0 // 4
뛰어넘으려는 시도: 2,0
뛰어넘으려는 시도: 2,0
뛰어넘으려는 시도: 2,0
1,3 // 4
뛰어넘으려는 시도: 1,3
뛰어넘기 검사중...: 0,1 // 0
뛰어넘으려는 시도: 1,3
뛰어넘기 검사중...: 0,1 // 0
뛰어넘으려는 시도: 1,3
뛰어넘기 검사중...: 0,1 // 0
3,0 // 5
뛰어넘으려는 시도: 3,0
뛰어넘으려는 시도: 3,0
2,3 // 5
뛰어넘으려는 시도: 2,3
뛰어넘기 검사중...: 0,2 // 0
뛰어넘기 검사중...: 1,1 // 0
뛰어넘으려는 시도: 2,3
뛰어넘기 검사중...: 0,2 // 0
뛰어넘기 검사중...: 1,1 // 0
뛰어넘으려는 시도: 2,3
뛰어넘기 검사중...: 0,2 // 0
뛰어넘기 검사중...: 1,1 // 0
3,3 // 6
6
https://ideone.com/EEgW2f
language:
Java (HotSpot 12)
created:
1 year 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!