24h購物| | PChome| 登入
2014-02-17 22:55:56| 人氣1,186| 回應0 | 上一篇 | 下一篇

[UVA] 11140 - Little Ali's Little Brother

推薦 0 收藏 0 轉貼0 訂閱站台

Problem A
 Little Ali's Little Brother!
Time Limit: 1 Second

 

Little Ali has a cute little brother. Recently, their father has bought them a strange puzzle. The pieces of this puzzle has horizontal or vertical edges (See figure below).

Some sample pieces of a puzzle

Since Little Ali loves his brother too much, he decided to entertain him with a challenging task! He gave his brother the puzzle board and some pieces, not necessarily fitting in the board. Little Ali does not want to trouble his little brother, so he decided to select the pieces that can fit in the board without any rotation. Now, he needs your help to decide if a piece can be placed appropriately in the board or not.

 

Input

The input begins with a single integer T in a line representing the number of test cases. Then, T test cases follow. Each test case begins with the specification of a board, which is an N x M grid. In the first line of each test case, there are three integers N, M, S (0<N, M<=50, 0<S<=10) in a single line representing the number of rows and columns of the board and the number of  pieces respectively. After that, N lines follow each containing exactly M characters where ‘*’ denotes a cell of the board that a piece can occupy it and  ‘.’ for the cells which the piece cannot occupy it. Afterwards, S blocks follow that each block contain specification of a piece. Specification of each block begins with two integers in a single line n, m (0<n, m<=50) representing the number of rows and columns of a rectangle box containing the piece (not necessarily minimum bounding box). Then, n lines follow each containing exactly m characters specifying a piece where ‘*’ denotes a cell belonging to the piece and ‘.’ denotes a cell not belonging to the piece. There is a blank line after each test case.

 

Output

For each piece of a test case, you must print “Yes” in the single line if this piece can be placed on the corresponding board and “No” otherwise. Print a blank line after each test case.

 

Sample Input
Sample Output

2

5 5 2

....*

...**

..***

...**

....*

3 2

**

**

**

1 6

******

 

3 3 1

***

*.*

***

3 2

**

.*

**

 

Yes

No

 

Yes

 

Problem setter: Mohammad Reza Khani

1st Amirkabir UT Annual Programming Contest  Final Round


查找圖是否為另一張圖的子圖。

#include <stdio.h>
using namespace std;
char g[55][55], mg[55][55];
int subImg(int N, int M, int n, int m) {
    int i, j, k, p, q;
    for(i = -N; i < N; i++) {
        for(j = -M; j < M; j++) {
            int ok = 1;
            for(p = 0; p < n; p++) {
                for(q = 0; q < m; q++) {
                    if(mg[p][q] == '.')
                        continue;
                    if(p+i < 0 || p+i >= N || q+j < 0 || q+j >= M)
                        ok = 0, p = n, q = m;
                    else {
                        if(g[p+i][q+j] == '.')
                            ok = 0, p = n, q = m;
                    }
                }
            }
            if(ok)    return 1;
        }
    }
    return 0;
}
int main() {
    int testcase;
    int n, m, N, M, q;
    int i, j, k;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &N, &M, &q);
        for(i = 0; i < N; i++)
            scanf("%s", &g[i]);
        while(q--) {
            scanf("%d %d", &n, &m);
            for(i = 0; i < n; i++)
                scanf("%s", &mg[i]);
            int sub = subImg(N, M, n, m);
            puts(sub ? "Yes" : "No");
        }
        puts("");
    }
    return 0;
}
// more ...
// http://mypaper.pchome.com.tw/zerojudge/post/1326705427
// ZOJ 1637 - Fast Image Match
// algorithm : FFT

台長: Morris
人氣(1,186) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 11160 - Going Together
此分類上一篇:[UVA][三分] 11232 - Cylinder

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文