星空

描述

Recently Little Hi started to like astronomy and downloaded the pictures of K constellations. He wonders how many of them he can spot in the night?

輸入

Line 1: K(1 <= K <= 20), the number of constellations.

K constellation pictures follow. The format of each picture is:

Line 1 of each picture: H and W(5 <= H, W, <= 100), the height and width of the picture.

Line 2~H+1 of each picture: An H*W matrix of characters representing the picture of a constellation. Each line contains W characters. ‘#’ for a star and ‘.’ for empty area. There are no more than 20 stars in each constellation.

After K constellations is the sky Little Hi looks to in the night.

Line 1 of sky: N and M(100 <= N, M <= 1000), the size of the sky Little Hi looks to.

Line 2~N of sky: An N*M matrix of characters representing the sky Little Hi looks to. Each line contains M characters. ‘#’ for a star and ‘.’ for empty area. There are no more than 5000 stars in the sky.

輸出

For each constellation in the Input output “Yes” or “No” indicating whether Little Hi can spot the constellation in the sky.

All pictures of constellations and the sky Little Hi looks to are in the same direction so there is no need to rotate the pictures.

提示

A constellation can be spoted if and only if all stars in the constellation can be matched in the sky. It is allowed that two spoted constellations share common stars.

原題見：http://hihocoder.com/contest/hiho71/problem/1

解法：

由于每個constellation中star最多有20個，可以将其位置坐标存儲下來。然後判斷時，枚舉天空的每個位置為初始位置，判斷偏移後的坐标是否為星，如果全部都符合，就輸出yes。

這裡有個坑，給的星圖可能有大片空白，而提示中說道隻要星星的位置比對就行，下面看個例子：

星圖為：

…….

……#

……#

sky為：

#

#

這種情況下可以找到星圖的，但是整個星圖是比sky還大的，是以我們要先将星圖中的空白去除。也就是計算出現#的最小x，和最小y作為星圖的相對起始點。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
enum {maxn = +};
char map[maxn][maxn];
struct star{
    int x, y;
};
struct star Const[][];
int starNum[];
char str[+][+];
 int m, n;
 bool has(int i)
 {
     for (int y = ; y < n; y++)
        for (int x =; x< m; x++)
     {
         int k;
         for (k=; k<starNum[i]; k++)
         {
             int nowX = x + Const[i][k].x;
             int nowY = y + Const[i][k].y;
             if (nowX >= m || nowY >= n || map[nowY][nowX] != '#')
                break;
         }
         if (k == starNum[i])
            return true;
     }
    return false;
 }
 //#define OJ
int main()
{
    #ifndef OJ
    freopen("in.txt", "r", stdin);
    #endif // OJ
    int k=;
    scanf("%d", &k);
    for (int i=; i< k; i++)
    {
        int h, w;
        scanf("%d %d", &h, &w);
        starNum[i] = ;
        for (int y = ; y< h; y++)
            scanf("%s", &(str[y]));
        int startx, starty;
        bool flag = false;
        for (startx = ; startx <w&& flag == false; )
        {
            for (int j=; j<h&& flag == false; j++)
                if (str[j][startx] == '#')
                {
                     flag = true;
                }
            if(flag == false)
                startx++;
        }
        flag = false;
        for (starty =; starty<h && flag == false; )
        {
            for (int j=; j< w && flag == false; j++)
                if (str[starty][j] == '#')
                    flag = true;
            if (flag == false)
                starty++;
        }
        for (int y = starty; y<h; y++)
        {
            for (int x = startx; x <w; x++)
            {
                if (str[y][x]== '#')
                {
                    Const[i][starNum[i]].x = x-startx;
                    Const[i][starNum[i]].y = y-starty;
                   // printf("const %d star %d x %d y %d\n", i, starNum[i], x, y);
                    starNum[i]++;
                }
            }
        }
    }

    scanf("%d %d", &n, &m);
    for (int i=; i< n; i++)
       scanf("%s", &(map[i]));
    for (int i=; i<k; i++)
    {
        if (has(i))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return ;

}