本文介绍了程序设计竞赛问：计数Polyominos的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
请看看我自己的答案，我想我做到了！
您好，
对于一个编程竞赛的一个例子的问题是写一个程序，找出有多少polyominos是可能的石头给定数。
因此，对于两块石头（ N = 2 ），只有一个polyominos：
XX
您可能认为这是第二个解决办法：
X X
但事实并非如此。该polyominos不是唯一的，如果你可以旋转。
因此，对于4结石（ N = 4 ），有7解决方法：
X X XX X X X X X X XX X XX XX XX X X X XX X X XX
应用程序必须能够找到解决方案 1＆LT; = N＆LT; = 10
PS：使用维基百科 polyominos的名单是不允许的;）
编辑：当然，问题是：如何做到这一点在Java中，C / C ++，C＃
我开始这个项目的Java。但后来我不得不承认，我不知道如何使用一个有效的算法来构建polyominos。
这是我到目前为止有：
进口的java.util.ArrayList;
进口的java.util.List;
公共类主
{
私人诠释countPolyminos（INT N）
{
hashes.clear（）;
计数= 0;
布尔[] []矩阵=新的布尔[N] [N];
createPolyominos（矩阵，N）;
返回计数;
}
私人列表＆LT;整数GT;哈希=新的ArrayList＆LT;整数GT;（）;
私人诠释计数;
私人无效createPolyominos（布尔[] []矩阵，INT N）
{
如果（N == 0）
{
布尔[] []裁剪= cropMatrix（矩阵）;
INT哈希= hashMatrixOrientationIndependent（矩阵）;
如果（！hashes.contains（散））
{
算上++;
hashes.add（散）;
}
返回;
}
//这里是真正的麻烦！
//然后这里是这样; createPolyominos（基质中，n-1）;
//但是，我们必须记住，该polyominos可以有分歧
}
公共布尔[] []副本（布尔[] []矩阵）
{
布尔[] [] B =新的布尔[matrix.length] [矩阵[0] .length];
的for（int i = 0; I＆LT; matrix.length ++ I）
{
System.arraycopy（矩阵[I]，0，B，0，矩阵[I] .length）;
}
返回b;
}
公共布尔[] [] cropMatrix（布尔[] []矩阵）
{
int类型l = 0，T = 0，R = 0时，b = 0;
// 剩下
左：为（INT X = 0，X＆LT; matrix.length ++ x）
{
对于（INT Y = 0; Y＆LT;基质[X] .length; + Y）
{
如果（矩阵[X] [Y]）
{
打破左边;
}
}
升++;
}
// 对
右：为（INT X = matrix.length - 1; X＆GT; = 0; --x）
{
对于（INT Y = 0; Y＆LT;基质[X] .length; + Y）
{
如果（矩阵[X] [Y]）
{
打破权利;
}
}
- [R ++;
}
// 最佳
顶部：为（INT Y = 0; Y＆LT;基质[0] .length; + Y）
{
为（中间体X = 0 X - 其中; matrix.length ++ x）的
{
如果（矩阵[X] [Y]）
{
破顶;
}
}
牛逼++;
}
// 底部
底部：为（INT Y =矩阵[0] .length; Y＆GT; = 0; --Y）
{
为（中间体X = 0 X - 其中; matrix.length ++ x）的
{
如果（矩阵[X] [Y]）
{
破底;
}
}
b ++;
}
//执行真正的作物
布尔[] [] =冒出新的布尔[matrix.length - 1 - R] [矩阵[0] .length - 笔 - B];
对于（INT为X = L，X＆LT; matrix.length - R的; ++ x）
{
System.arraycopy（矩阵[X - 1]，T，裁剪，0，矩阵[X] .length - 笔 - B）;
}
回报裁剪;
}
公众诠释hashMatrix（布尔[] []矩阵）
{
INT散列= 0;
为（中间体X = 0 X - 其中; matrix.length ++ x）的
{
对于（INT Y = 0; Y＆LT;基质[X] .length; + Y）
{
哈希+ =矩阵[X] [Y] （（（X + 7）所述; 4;）*（（Y + 3）＆其中;＆10 6）* 31）：（（（（X + 5）＆其中;＆10 9）*（（（Y + x）的+ 18）其中; 7;）* 53））;
}
}
返回哈希;
}
公众诠释hashMatrixOrientationIndependent（布尔[] []矩阵）
{
INT散列= 0;
哈希+ = hashMatrix（矩阵）;
对（INT I = 0;我3; ++ⅰ）
{
矩阵= rotateMatrixLeft（矩阵）;
哈希+ = hashMatrix（矩阵）;
}
返回哈希;
}
公共布尔[] [] rotateMatrixRight（布尔[] []矩阵）
{
/ *宽和高都已经换* /
INT W = matrix.length;
INT H =矩阵[0] .length;
布尔[] [] =保留新的布尔并[h] [瓦特];
的for（int i = 0; I＆LT; H ++ I）
{
对于（INT J = 0; J＆LT;瓦; ++ j）条
{
保留[I] [j]的矩阵= [瓦特 - J - 1] [I];
}
}
返回RET;
}
公共布尔[] [] rotateMatrixLeft（布尔[] []矩阵）
{
/ *宽和高都已经换* /
INT W = matrix.length;
INT H =矩阵[0] .length;
布尔[] [] =保留新的布尔并[h] [瓦特];
的for（int i = 0; I＆LT; H ++ I）
{
对于（INT J = 0; J＆LT;瓦; ++ j）条
{
RET [I] [J] =矩阵[J]。[H - 我 - 1];
}
}
返回RET;
}
}
解决方案
我想我做到了！
编辑：我使用的是 SHA-256 算法来哈希他们，现在它的工作原理正确
下面是结果：
numberOfStones - ＆GT; numberOfPolyominos
1 - ＆GT; 1
2 - ＆GT; 1
3 - ＆GT; 2
4 - ＆GT; 7
5 - ＆GT; 18
6 - ＆GT; 60
7 - ＆GT; 196
8 - ＆GT; 704
9 - ＆GT; 2500
10 - ＆GT;终止
下面是code（JAVA）：
进口java.io.BufferedReader中;
进口java.io.IOException异常;
进口java.io.InputStreamReader中;
进口的java.util.ArrayList;
进口的java.util.List;
/ * VPW模板* /
公共类主
{
/ **
* @参数ARGS
* /
公共静态无效的主要（字串[] args）抛出IOException异常
{
新的Main（）开始（）;
}
公共无效启动（）抛出IOException异常
{
/ *阅读的东西* /
的BufferedReader BR =新的BufferedReader（新的InputStreamReader（System.in））;
的String []输入=新的String [的Integer.parseInt（br.readLine（））;
的for（int i = 0; I＆LT; input.length ++ I）
{
输入[I] = br.readLine（）;
}
/ *过程的每一行* /
的for（int i = 0; I＆LT; input.length ++ I）
{
ProcessLine从（输入[I]）;
}
}
公共无效ProcessLine从（串线）
{
INT N =的Integer.parseInt（线）;
的System.out.println（countPolyminos（N））;
}
私人诠释countPolyminos（INT N）
{
hashes.clear（）;
计数= 0;
布尔[] []矩阵=新的布尔[N] [N];
矩阵[N / 2] [N / 2] =真;
createPolyominos（矩阵，N - 1）;
返回计数;
}
私人列表＆LT; BigInteger的＆GT;哈希=新的ArrayList＆LT; BigInteger的＆GT;（）;
私人诠释计数;
私人无效createPolyominos（布尔[] []矩阵，INT N）
{
如果（N == 0）
{
布尔[] []裁剪= cropMatrix（矩阵）;
BigInteger的哈希值= hashMatrixOrientationIndependent（裁剪）;
如果（！hashes.contains（散））
{
//的System.out.println（计数+找到了！）;
// printMatrix（裁剪）;
//的System.out.println（）;
算上++;
hashes.add（散）;
}
返回;
}
为（中间体X = 0 X - 其中; matrix.length ++ x）的
{
对于（INT Y = 0; Y＆LT;基质[X] .length; + Y）
{
如果（矩阵[X] [Y]）
{
如果（！X - →0＆安培;＆安培;矩阵[X - 1] [Y]）
{
布尔[] []克隆=拷贝（矩阵）;
克隆[X - 1] [Y] =真;
createPolyominos（克隆，N - 1）;
}
如果（X＆LT; matrix.length - 1安培;＆放大器;矩阵[X + 1] [Y]！）
{
布尔[] []克隆=拷贝（矩阵）;
克隆[X + 1] [Y] =真;
createPolyominos（克隆，N - 1）;
}
如果（γ大于0＆安培;＆安培;！矩阵[X] [Y - 1]）
{
布尔[] []克隆=拷贝（矩阵）;
克隆[X] [Y - 1] =真;
createPolyominos（克隆，N - 1）;
}
如果（Y＆LT;基质[X] .length - 1安培;！＆放大器;矩阵[X] [Y + 1]）
{
布尔[] []克隆=拷贝（矩阵）;
克隆[X] [Y + 1] =真;
createPolyominos（克隆，N - 1）;
}
}
}
}
}
公共布尔[] []副本（布尔[] []矩阵）
{
布尔[] [] B =新的布尔[matrix.length] [矩阵[0] .length];
的for（int i = 0; I＆LT; matrix.length ++ I）
{
System.arraycopy（矩阵[I]，0，B [I] 0，矩阵[I] .length）;
}
返回b;
}
公共无效printMatrix（布尔[] []矩阵）
{
对于（INT Y = 0; Y＆LT; matrix.length ++ Y）
{
对于（INT X = 0，X＆LT;矩阵[Y] .length; + X）
{
System.out.print（（矩阵[Y] [X]'X'：''））;
}
的System.out.println（）;
}
}
公共布尔[] [] cropMatrix（布尔[] []矩阵）
{
int类型l = 0，T = 0，R = 0时，b = 0;
// 剩下
左：为（INT X = 0，X＆LT; matrix.length ++ x）
{
对于（INT Y = 0; Y＆LT;基质[X] .length; + Y）
{
如果（矩阵[X] [Y]）
{
打破左边;
}
}
升++;
}
// 对
右：为（INT X = matrix.length - 1; X＆GT; = 0; --x）
{
对于（INT Y = 0; Y＆LT;基质[X] .length; + Y）
{
如果（矩阵[X] [Y]）
{
打破权利;
}
}
- [R ++;
}
// 最佳
顶部：为（INT Y = 0; Y＆LT;基质[0] .length; + Y）
{
为（中间体X = 0 X - 其中; matrix.length ++ x）的
{
如果（矩阵[X] [Y]）
{
破顶;
}
}
牛逼++;
}
// 底部
底部：为（INT Y =矩阵[0] .length - 1; Y＆GT; = 0; --Y）
{
为（中间体X = 0 X - 其中; matrix.length ++ x）的
{
如果（矩阵[X] [Y]）
{
破底;
}
}
b ++;
}
//执行真正的作物
布尔[] [] =冒出新的布尔[matrix.length - 1 - R] [矩阵[0] .length - 笔 - B];
对于（INT为X = L，X＆LT; matrix.length - R的; ++ x）
{
System.arraycopy（矩阵[X]，T，裁剪[X - 1]，0，矩阵[X] .length - 笔 - B）;
}
回报裁剪;
}
公众的BigInteger hashMatrix（布尔[] []矩阵）
{
尝试
{
消息摘要MD = MessageDigest.getInstance（SHA-256）;
md.update（（字节）matrix.length）;
md.update（（字节）矩阵[0] .length）;
为（中间体X = 0 X - 其中; matrix.length ++ x）的
{
对于（INT Y = 0; Y＆LT;基质[X] .length; + Y）
{
如果（矩阵[X] [Y]）
{
md.update（（字节）X）;
} 其他
{
md.update（（字节）Y）;
}
}
}
返回新的BigInteger（1，md.digest（））;
}赶上（抛出：NoSuchAlgorithmException E）
{
System.exit（1）;
返回null;
}
}
公众的BigInteger hashMatrixOrientationIndependent（布尔[] []矩阵）
{
BigInteger的哈希值= hashMatrix（矩阵）;
对（INT I = 0;我3; ++ⅰ）
{
矩阵= rotateMatrixLeft（矩阵）;
散列= hash.add（hashMatrix（矩阵））;
}
返回哈希;
}
公共布尔[] [] rotateMatrixRight（布尔[] []矩阵）
{
/ *宽和高都已经换* /
INT W = matrix.length;
INT H =矩阵[0] .length;
布尔[] [] =保留新的布尔并[h] [瓦特];
的for（int i = 0; I＆LT; H ++ I）
{
对于（INT J = 0; J＆LT;瓦; ++ j）条
{
保留[I] [j]的矩阵= [瓦特 - J - 1] [I];
}
}
返回RET;
}
公共布尔[] [] rotateMatrixLeft（布尔[] []矩阵）
{
/ *宽和高都已经换* /
INT W = matrix.length;
INT H =矩阵[0] .length;
布尔[] [] =保留新的布尔并[h] [瓦特];
的for（int i = 0; I＆LT; H ++ I）
{
对于（INT J = 0; J＆LT;瓦; ++ j）条
{
RET [I] [J] =矩阵[J]。[H - 我 - 1];
}
}
返回RET;
}
Please see my own answer, I think I did it!
Hi,
An example question for a programming contest was to write a program that finds out how much polyominos are possible with a given number of stones.
So for two stones (n = 2) there is only one polyominos:
XX
You might think this is a second solution:
X
X
But it isn't. The polyominos are not unique if you can rotate them.
So, for 4 stones (n = 4), there are 7 solutions:
X
X XX X X X X
X X XX X XX XX XX
X X X XX X X XX
The application has to be able to find the solution for 1 <= n <=10
PS: Using the list of polyominos on Wikipedia isn't allowed ;)
EDIT: Of course the question is: How to do this in Java, C/C++, C#
I started this project in Java. But then I had to admit I didn't know how to build polyominos using an efficient algorithm.
This is what I had so far:
import java.util.ArrayList;
import java.util.List;
public class Main
{
private int countPolyminos(int n)
{
hashes.clear();
count = 0;
boolean[][] matrix = new boolean[n][n];
createPolyominos(matrix, n);
return count;
}
private List<Integer> hashes = new ArrayList<Integer>();
private int count;
private void createPolyominos(boolean[][] matrix, int n)
{
if (n == 0)
{
boolean[][] cropped = cropMatrix(matrix);
int hash = hashMatrixOrientationIndependent(matrix);
if (!hashes.contains(hash))
{
count++;
hashes.add(hash);
}
return;
}
// Here is the real trouble!!
// Then here something like; createPolyominos(matrix, n-1);
// But, we need to keep in mind that the polyominos can have ramifications
}
public boolean[][] copy(boolean[][] matrix)
{
boolean[][] b = new boolean[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; ++i)
{
System.arraycopy(matrix[i], 0, b, 0, matrix[i].length);
}
return b;
}
public boolean[][] cropMatrix(boolean[][] matrix)
{
int l = 0, t = 0, r = 0, b = 0;
// Left
left: for (int x = 0; x < matrix.length; ++x)
{
for (int y = 0; y < matrix[x].length; ++y)
{
if (matrix[x][y])
{
break left;
}
}
l++;
}
// Right
right: for (int x = matrix.length - 1; x >= 0; --x)
{
for (int y = 0; y < matrix[x].length; ++y)
{
if (matrix[x][y])
{
break right;
}
}
r++;
}
// Top
top: for (int y = 0; y < matrix[0].length; ++y)
{
for (int x = 0; x < matrix.length; ++x)
{
if (matrix[x][y])
{
break top;
}
}
t++;
}
// Bottom
bottom: for (int y = matrix[0].length; y >= 0; --y)
{
for (int x = 0; x < matrix.length; ++x)
{
if (matrix[x][y])
{
break bottom;
}
}
b++;
}
// Perform the real crop
boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b];
for (int x = l; x < matrix.length - r; ++x)
{
System.arraycopy(matrix[x - l], t, cropped, 0, matrix[x].length - t - b);
}
return cropped;
}
public int hashMatrix(boolean[][] matrix)
{
int hash = 0;
for (int x = 0; x < matrix.length; ++x)
{
for (int y = 0; y < matrix[x].length; ++y)
{
hash += matrix[x][y] ? (((x + 7) << 4) * ((y + 3) << 6) * 31) : ((((x+5) << 9) * (((y + x) + 18) << 7) * 53));
}
}
return hash;
}
public int hashMatrixOrientationIndependent(boolean[][] matrix)
{
int hash = 0;
hash += hashMatrix(matrix);
for (int i = 0; i < 3; ++i)
{
matrix = rotateMatrixLeft(matrix);
hash += hashMatrix(matrix);
}
return hash;
}
public boolean[][] rotateMatrixRight(boolean[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
boolean[][] ret = new boolean[h][w];
for (int i = 0; i < h; ++i)
{
for (int j = 0; j < w; ++j)
{
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public boolean[][] rotateMatrixLeft(boolean[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
boolean[][] ret = new boolean[h][w];
for (int i = 0; i < h; ++i)
{
for (int j = 0; j < w; ++j)
{
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
}
解决方案
I think I did it!
EDIT: I'm using the SHA-256 algorithm to hash them, now it works correct.
Here are the results:
numberOfStones -> numberOfPolyominos
1 -> 1
2 -> 1
3 -> 2
4 -> 7
5 -> 18
6 -> 60
7 -> 196
8 -> 704
9 -> 2500
10 -> terminated
Here is the code (Java):
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
/* VPW Template */
public class Main
{
/**
* @param args
*/
public static void main(String[] args) throws IOException
{
new Main().start();
}
public void start() throws IOException
{
/* Read the stuff */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = new String[Integer.parseInt(br.readLine())];
for (int i = 0; i < input.length; ++i)
{
input[i] = br.readLine();
}
/* Process each line */
for (int i = 0; i < input.length; ++i)
{
processLine(input[i]);
}
}
public void processLine(String line)
{
int n = Integer.parseInt(line);
System.out.println(countPolyminos(n));
}
private int countPolyminos(int n)
{
hashes.clear();
count = 0;
boolean[][] matrix = new boolean[n][n];
matrix[n / 2][n / 2] = true;
createPolyominos(matrix, n - 1);
return count;
}
private List<BigInteger> hashes = new ArrayList<BigInteger>();
private int count;
private void createPolyominos(boolean[][] matrix, int n)
{
if (n == 0)
{
boolean[][] cropped = cropMatrix(matrix);
BigInteger hash = hashMatrixOrientationIndependent(cropped);
if (!hashes.contains(hash))
{
// System.out.println(count + " Found!");
// printMatrix(cropped);
// System.out.println();
count++;
hashes.add(hash);
}
return;
}
for (int x = 0; x < matrix.length; ++x)
{
for (int y = 0; y < matrix[x].length; ++y)
{
if (matrix[x][y])
{
if (x > 0 && !matrix[x - 1][y])
{
boolean[][] clone = copy(matrix);
clone[x - 1][y] = true;
createPolyominos(clone, n - 1);
}
if (x < matrix.length - 1 && !matrix[x + 1][y])
{
boolean[][] clone = copy(matrix);
clone[x + 1][y] = true;
createPolyominos(clone, n - 1);
}
if (y > 0 && !matrix[x][y - 1])
{
boolean[][] clone = copy(matrix);
clone[x][y - 1] = true;
createPolyominos(clone, n - 1);
}
if (y < matrix[x].length - 1 && !matrix[x][y + 1])
{
boolean[][] clone = copy(matrix);
clone[x][y + 1] = true;
createPolyominos(clone, n - 1);
}
}
}
}
}
public boolean[][] copy(boolean[][] matrix)
{
boolean[][] b = new boolean[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; ++i)
{
System.arraycopy(matrix[i], 0, b[i], 0, matrix[i].length);
}
return b;
}
public void printMatrix(boolean[][] matrix)
{
for (int y = 0; y < matrix.length; ++y)
{
for (int x = 0; x < matrix[y].length; ++x)
{
System.out.print((matrix[y][x] ? 'X' : ' '));
}
System.out.println();
}
}
public boolean[][] cropMatrix(boolean[][] matrix)
{
int l = 0, t = 0, r = 0, b = 0;
// Left
left: for (int x = 0; x < matrix.length; ++x)
{
for (int y = 0; y < matrix[x].length; ++y)
{
if (matrix[x][y])
{
break left;
}
}
l++;
}
// Right
right: for (int x = matrix.length - 1; x >= 0; --x)
{
for (int y = 0; y < matrix[x].length; ++y)
{
if (matrix[x][y])
{
break right;
}
}
r++;
}
// Top
top: for (int y = 0; y < matrix[0].length; ++y)
{
for (int x = 0; x < matrix.length; ++x)
{
if (matrix[x][y])
{
break top;
}
}
t++;
}
// Bottom
bottom: for (int y = matrix[0].length - 1; y >= 0; --y)
{
for (int x = 0; x < matrix.length; ++x)
{
if (matrix[x][y])
{
break bottom;
}
}
b++;
}
// Perform the real crop
boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b];
for (int x = l; x < matrix.length - r; ++x)
{
System.arraycopy(matrix[x], t, cropped[x - l], 0, matrix[x].length - t - b);
}
return cropped;
}
public BigInteger hashMatrix(boolean[][] matrix)
{
try
{
MessageDigest md = MessageDigest.getInstance("SHA-256");
md.update((byte) matrix.length);
md.update((byte) matrix[0].length);
for (int x = 0; x < matrix.length; ++x)
{
for (int y = 0; y < matrix[x].length; ++y)
{
if (matrix[x][y])
{
md.update((byte) x);
} else
{
md.update((byte) y);
}
}
}
return new BigInteger(1, md.digest());
} catch (NoSuchAlgorithmException e)
{
System.exit(1);
return null;
}
}
public BigInteger hashMatrixOrientationIndependent(boolean[][] matrix)
{
BigInteger hash = hashMatrix(matrix);
for (int i = 0; i < 3; ++i)
{
matrix = rotateMatrixLeft(matrix);
hash = hash.add(hashMatrix(matrix));
}
return hash;
}
public boolean[][] rotateMatrixRight(boolean[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
boolean[][] ret = new boolean[h][w];
for (int i = 0; i < h; ++i)
{
for (int j = 0; j < w; ++j)
{
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public boolean[][] rotateMatrixLeft(boolean[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
boolean[][] ret = new boolean[h][w];
for (int i = 0; i < h; ++i)
{
for (int j = 0; j < w; ++j)
{
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
这篇关于程序设计竞赛问：计数Polyominos的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！