Finding the number of possible squares in this picture
The following is a visual problem I came across today. The question here is simply how many squares there are in the picture.
How would you go about solving something like this though code ? Furthermore, if the actual picture isn't processed, how would you go about modelling it ?
PS: I sense that the actual resolution would require a rule to define what can be considered as a square. Something along the lines of saying that sides are equal in length and can be composed of any number of segments as long as they fit within the enclosing square. I'm not sure how you could represent a position though.
If you can model this as a matrix, then the only information you need is the position of vertices. Then for every vertex check all the vertices in the same row and for each of found vertex check their column. then delete the processed vertex. Do the same column-wise. The worst case complexity would be n! (?)
I added the code for clarification.
public class SqFinder {
int calculateSquares(int[][] vertices, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (vertices[i][j] == 1) {
for (int k = 1; k < n-j; k++) {
if (i + k < n && vertices[i][j+k] == 1 && vertices[i + k][j] == 1 && vertices[i + k][j + k] == 1)
count++;
}
}
vertices[i][j] =0;
}
}
return count;
}
public static void main(String[] args) {
SqFinder a = new SqFinder();
// int [][] test = {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};
int [][] test = {{1,1,1},{1,1,1},{1,1,1}};
System.out.println(a.calculateSquares(test, 3));
}
}
最简单的方法是循环遍历每个顶点，并检查它是否可以是宽度为1的正方形的左上顶点，然后是宽度为2，等于3的左上角的顶点
Encoding: what you have is a network. Encode this as a network connecting nodes situated in a discrete two-dimensional space.
The question is really asking you to count the number of paths that meet the following properties:
A turn in this case is when either (a) if the previous move resulted in a change in the y-co-ordinate, this move results in a change in the x-co-ordinate; or (b) if the previous move resulted in a change in the x-co-ordinate, this move results in a change in the y-co-ordinate.
As to keeping track of the process: The best suggestions I've seen on this page are simply to iterate over each node, and for each such node to check all possible sizes of square. That should obviate the need to keep track any further.
If you have a smarter method, as long as your paths are always left-handed or always right-handed, each square is uniquely identified by the starting vertex, and length of side.
链接地址: http://www.djcxy.com/p/11054.html上一篇: 如何在中间搜索freebase
下一篇: 在这幅图中找到可能的正方形数量