2014
02-24

Overlapping Squares

In most puzzles we are given some pieces and we have to make a target pattern which can be built in only one possible way. But some puzzles are a bit different, we are given a target pattern and from that target pattern we have to find in how many ways the pieces can be placed. Such a puzzle is the puzzle of overlapping squares. To understand this puzzle, look at the pictures below:

[tu pian]
In first figure we have placed a (2×2) filled square in a (4×4) grid. In the second figure we have placed another (2×2) filled square in the grid, which have of course deleted some part of the black lines of the previous square, in third picture we have placed a third square and in the fourth picture we have placed a fourth square. The picture can become even more complex if we place more (2×2) squares. Write a program to determine if it’s possible to form a target image using at most six pieces of 2×2 squares.

The input consists of several test cases. Each test case is contained in five lines and each line contains nine characters. If the horizontal border of a filled square is visible it is denoted with ‘_’ (ASCII value 95) sign and if vertical border of a filled square is visible then it is denoted with ‘|’ (ASCII value 124) character. The board contains no other character than ‘_’, ‘|’ and of course ‘ ’ (ASCII Value 32). The border lines of the squares can only be along the grid lines. Each board lines end with a ‘#’ (Hash character) which denotes the end of line. This character is not a part of the grid or square. The last test case is followed by a single zero, which should not be processed.

The input consists of several test cases. Each test case is contained in five lines and each line contains nine characters. If the horizontal border of a filled square is visible it is denoted with ‘_’ (ASCII value 95) sign and if vertical border of a filled square is visible then it is denoted with ‘|’ (ASCII value 124) character. The board contains no other character than ‘_’, ‘|’ and of course ‘ ’ (ASCII Value 32). The border lines of the squares can only be along the grid lines. Each board lines end with a ‘#’ (Hash character) which denotes the end of line. This character is not a part of the grid or square. The last test case is followed by a single zero, which should not be processed.

         #
_ _ _   #
| |_ _|  #
|_|   |  #
|_ _|  #
#
_ _   #
|   |  #
|_ _|  #
#
_ _ _ _ #
|_|_|_|_|#
|_|_|_|_|#
|_|_|_|_|#
|_|_|_|_|#
_ _   #
_|   |_ #
| |_ _| |#
|_|   |_|#
|_ _|_|#
0

Case 1: Yes
Case 2: Yes
Case 3: No
Case 4: Yes

/**********************************************************************
Author: hanshuai
Created Time:  2011/2/18 13:57:38
File Name: j.cpp
Description:
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

char tg[10][10] = {
" _ _ ",
"|   |",
"|_ _|"
};
struct Grid{
char s[5][12];
bool input(){
for(int i = 0; i < 5; i ++) if(!gets(s[i])) return false;
return true;
}
void output(){
for(int i = 0; i < 5; i ++) printf("%s\n", s[i]);
printf("\n");
}
bool move(int x, int y){
for(int i = 0; i <= 2; i ++){
for(int j = 0; j <= 4; j ++){
if(i == 0 && (j == 0 || j == 2 || j == 4)) continue;
if(s[x+i][y+j] == tg[i][j]) s[x+i][y+j] = '.';
if(s[x+i][y+j] == '.') continue;
return false;
}
}
return true;
}
bool ok(){
for(int i = 0; i < 5; i ++){
for(int j = 0; j < 9; j ++){
if(s[i][j] != '.' && s[i][j] != ' ') return false;
}
}
return true;
}
}g[8];
bool dfs(int th){
if(g[th].ok()) return true;
if(th == 6) return false;
//    g[th].output();
for(int i = 0; i + 2 < 5; i ++){
for(int j = 0; j + 4 < 9; j += 2){
g[th+1] = g[th];
if(g[th+1].move(i, j)){
if(dfs(th+1)) return true;
}
}
}
return false;
}
int main() {
int cas = 0;
while(g[0].input()){
printf("Case %d: ", ++cas);
printf("%s\n", dfs(0) ? "Yes" : "No");
}
return 0;
}

1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

2. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}