fork download
copy 
  1. import java.util.*;
  2.  
  3. public class FoxConnection3
  4. {
  5. 	class Shape
  6. 	{
  7. 		public boolean[][] mat;
  8. 		Shape(boolean[][] input)
  9. 		{
  10. 			input = simpl(input);
  11. 			mat = new boolean[input.length][input[0].length];
  12. 			for(int i = 0; i < input.length; i++)
  13. 				for(int j = 0; j < input[0].length; j++)
  14. 					mat[i][j] = input[i][j];
  15. 		}
  16. 		boolean[][] simpl(boolean[][] mat)
  17. 		{
  18. 			int minX = mat.length, maxX = 0, minY = mat[0].length, maxY = 0;
  19. 			for(int i = 0; i < mat.length; i++)
  20. 				for(int j = 0; j < mat[0].length; j++)
  21. 					if(mat[i][j])
  22. 					{
  23. 						minX = Math.min(minX, i);
  24. 						maxX = Math.max(maxX, i);
  25. 						minY = Math.min(minY, j);
  26. 						maxY = Math.max(maxY, j);
  27. 					}
  28. 			boolean[][] ret = new boolean[maxX - minX + 1][maxY - minY + 1];
  29. 			for(int i = minX; i <= maxX; i++)
  30. 				for(int j = minY; j <= maxY; j++)
  31. 					ret[i - minX][j - minY] = mat[i][j];
  32. 			return ret;
  33. 		}
  34. 		public String getHash()
  35. 		{
  36. 			String ret = "";
  37. 			for(int i = 0; i < mat.length; i++)
  38. 			{
  39. 				for(int j = 0; j < mat[0].length; j++)
  40. 					if(mat[i][j])
  41. 						ret += "1";
  42. 					else
  43. 						ret += "0";
  44. 				ret += "\n";
  45. 			}
  46. 			return ret;
  47. 		}
  48. 		public int[] getPosition(int id)
  49. 		{
  50. 			int k = 0;
  51. 			for(int i = 0; i < mat.length; i++)
  52. 				for(int j = 0; j < mat[0].length; j++)
  53. 					if(mat[i][j])
  54. 					{
  55. 						if(k == id)
  56. 						{
  57. 							int[] ret = new int[2];
  58. 							ret[0] = i;
  59. 							ret[1] = j;
  60. 							return ret;
  61. 						}
  62. 						k ++;
  63. 					}
  64. 			return new int[2];
  65. 		}
  66. 	};
  67.  
  68. 	int k;
  69. 	int[] xs, ys;
  70. 	int[] p;
  71. 	Shape currentShape;
  72. 	long ret;
  73.  
  74. 	long calc()
  75. 	{
  76. 		long ret = 0;
  77. 		long[] t = new long[k];
  78. 		for(int i = 0; i < k; i++)
  79. 			t[i] = currentShape.getPosition(i)[0] - xs[p[i]];
  80. 		Arrays.sort(t);
  81. 		for(int i = 0; i < k; i++)
  82. 			ret += Math.abs(t[i] - t[k/2]);
  83. 		for(int i = 0; i < k; i++)
  84. 			t[i] = currentShape.getPosition(i)[1] - ys[p[i]];
  85. 		Arrays.sort(t);
  86. 		for(int i = 0; i < k; i++)
  87. 			ret += Math.abs(t[i] - t[k/2]);
  88. 		return ret;
  89. 	}
  90.  
  91. 	void dfs(int cur, int mask)
  92. 	{
  93. 		if(cur == k)
  94. 			ret = Math.min(ret, calc());
  95. 		else
  96. 		{
  97. 			for(int i = 0; i < k; i++)
  98. 				if(((1<<i)&mask) == 0)
  99. 				{
  100. 					p[cur] = i;
  101. 					dfs(cur + 1, mask | (1<<i));
  102. 				}
  103. 		}
  104. 	}
  105.  
  106. 	public long minimalSteps(int[] _x, int[] _y)
  107. 	{
  108. 		k = _x.length;
  109. 		int[] dx = {1, -1, 0, 0};
  110. 		int[] dy = {0, 0, 1, -1};
  111. 		xs = _x;
  112. 		ys = _y;
  113. 		p = new int[k];
  114. 		List < List <Shape> > shapes = new ArrayList < List < Shape> >();
  115. 		for(int i = 0; i < 9; i++)
  116. 			shapes.add(new ArrayList<Shape>());
  117. 		boolean[][] initShape = new boolean[1][1];
  118. 		initShape[0][0] = true;
  119. 		shapes.get(1).add(new Shape(initShape));
  120. 		Set <String> mem = new HashSet <String> ();
  121. 		mem.add(shapes.get(1).get(0).getHash());
  122. 		for(int i = 1; i < k; i++)
  123. 			for(int j = 0; j < shapes.get(i).size(); j++)
  124. 			{
  125. 				int n = shapes.get(i).get(j).mat.length + 2;
  126. 				int m = shapes.get(i).get(j).mat[0].length + 2;
  127. 				boolean[][] t = new boolean[n][m];
  128. 				for(int x = 0; x < n; x++)
  129. 					for(int y = 0; y < m; y++)
  130. 						if(1 <= x && x < n-1 && 1 <= y && y < m-1)
  131. 							t[x][y] = shapes.get(i).get(j).mat[x-1][y-1];
  132. 						else
  133. 							t[x][y] = false;
  134. 				for(int x = 0; x < n; x++)
  135. 					for(int y = 0; y < m; y++)
  136. 						if(1 <= x && x < n-1 && 1 <= y && y < m-1 && t[x][y])
  137. 							for(int dir = 0; dir < 4; dir++)
  138. 							{
  139. 								int nx = x + dx[dir];
  140. 								int ny = y + dy[dir];
  141. 								if(t[nx][ny] == false)
  142. 								{
  143. 									t[nx][ny] = true;
  144. 									Shape nextShape = new Shape(t);
  145. 									if(mem.contains(nextShape.getHash()) == false)
  146. 									{
  147. 										mem.add(nextShape.getHash());
  148. 										shapes.get(i+1).add(nextShape);
  149. 									}
  150. 									t[nx][ny] = false;
  151. 								}
  152. 							}
  153. 			}
  154.  
  155. 		ret = 1000000000000000000L;
  156.  
  157. 		for(int c = 0; c < shapes.get(k).size(); c++)
  158. 		{
  159. 			currentShape = shapes.get(k).get(c);
  160. 			dfs(0, 0);
  161. 		}
  162.  
  163. 		return ret;
  164. 	}
  165. }
  166.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:3: error: class FoxConnection3 is public, should be declared in a file named FoxConnection3.java
public class FoxConnection3
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/sbEZSH
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!