fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. public class FoxConnection4
  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. 	};
  49.  
  50. 	public int howManyWays(String[] board, int k)
  51. 	{
  52. 		int[] dx = {1, -1, 0, 0};
  53. 		int[] dy = {0, 0, 1, -1};
  54. 		List < List <Shape> > shapes = new ArrayList < List < Shape> >();
  55. 		for(int i = 0; i < 9; i++)
  56. 			shapes.add(new ArrayList<Shape>());
  57. 		boolean[][] initShape = new boolean[1][1];
  58. 		initShape[0][0] = true;
  59. 		shapes.get(1).add(new Shape(initShape));
  60. 		Set <String> mem = new HashSet <String> ();
  61. 		mem.add(shapes.get(1).get(0).getHash());
  62. 		for(int i = 1; i < k; i++)
  63. 			for(int j = 0; j < shapes.get(i).size(); j++)
  64. 			{
  65. 				int n = shapes.get(i).get(j).mat.length + 2;
  66. 				int m = shapes.get(i).get(j).mat[0].length + 2;
  67. 				boolean[][] t = new boolean[n][m];
  68. 				for(int x = 0; x < n; x++)
  69. 					for(int y = 0; y < m; y++)
  70. 						if(1 <= x && x < n-1 && 1 <= y && y < m-1)
  71. 							t[x][y] = shapes.get(i).get(j).mat[x-1][y-1];
  72. 						else
  73. 							t[x][y] = false;
  74. 				for(int x = 0; x < n; x++)
  75. 					for(int y = 0; y < m; y++)
  76. 						if(1 <= x && x < n-1 && 1 <= y && y < m-1 && t[x][y])
  77. 							for(int dir = 0; dir < 4; dir++)
  78. 							{
  79. 								int nx = x + dx[dir];
  80. 								int ny = y + dy[dir];
  81. 								if(t[nx][ny] == false)
  82. 								{
  83. 									t[nx][ny] = true;
  84. 									Shape nextShape = new Shape(t);
  85. 									if(mem.contains(nextShape.getHash()) == false)
  86. 									{
  87. 										mem.add(nextShape.getHash());
  88. 										shapes.get(i+1).add(nextShape);
  89. 									}
  90. 									t[nx][ny] = false;
  91. 								}
  92. 							}
  93. 			}
  94. 		int ret = 0;
  95. 		for(int i = 0; i < shapes.get(k).size(); i++)
  96. 		{
  97. 			int n = board.length;
  98. 			int m = board[0].length();
  99. 			Shape s = shapes.get(k).get(i);
  100. 			for(int x = 0; x + s.mat.length <= n; x++)
  101. 				for(int y = 0; y + s.mat[0].length <= m; y++)
  102. 				{
  103. 					boolean conflict = false;
  104. 					for(int px = 0; px < s.mat.length; px ++)
  105. 						for(int py = 0; py < s.mat[0].length; py ++)
  106. 							if(board[x+px].charAt(y+py) == '#' && s.mat[px][py] == true)
  107. 								conflict = true;
  108. 					if(!conflict)
  109. 						ret ++;
  110. 				}
  111. 		}
  112. 		return ret;
  113. 	}
  114. }
  115.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:3: error: class FoxConnection4 is public, should be declared in a file named FoxConnection4.java
public class FoxConnection4
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/TLoazT
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!