首页 > ACM题库 > HDU-杭电 > HDU 2937-Overlapping Squares[解题报告]HOJ
2014
02-24

HDU 2937-Overlapping Squares[解题报告]HOJ

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));
    }
    }

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。