All the uppercase English letters and decimal digits (total 36
characters) can be written in (16*43) grids (16 rows and 43 columns)
using dots ('.') and asterisks ('*'). Some such characters are shown
below. As you can see that the empty pixels are marked with '.'s and
black pixels are marked with '*'s.
When these characters are placed one over another (without scaling,
translation or rotation) it is very difficult to judge from above how
many characters are there in the pile. Sometimes it is also very
difficult to say which characters are in the pile but sometimes it is
very easy as you can tell whether a character is present in the pile
just by checking a single pixel (if the pixel is black the character is
present, otherwise absent). Suppose out of the 36 characters you have
specific grid representation of specific M characters with you. From those M
character grids your friend can choose any number of grids and place
them in any order to form a pile and then ask you to guess which
characters are present there. But you are clever and you know that there
are certain characters whose presence in the pile can be detected just
by checking a single pixel (regardless of whatever your friend does).
Given the characters in hand your job is to identify the characters
whose presence can be detected by checking only a single pixel.
There is only a single set of input.
First line of the input file contains two integers N (
1
N36) and Q (
1Q1000). Here N is the total number of character grids to consider for all the queries of this problem and Q denotes the total number of queries. The next line contains a string consisting exactly N
distinct uppercase alphanumerals. This string denotes the order in
which the description alpha-numeral grids will appear in the input. The
next 17N lines describe the grid for N
characters. Each character-grid is described in exactly 16 lines but
there is a line containing only empty pixels following the description
of each character.
Each of the next Q lines a string of M (
1M18)
characters which describes the set of characters from which your friend
can choose any number of character grids and place on a pile in any
order. All the characters in this query string will be distinct.
For each query produce one line of output. This line contains the serial of output followed by a string containing only `
N' or `
Y' (one for each character in the input query string). The printed character should be `
Y' if the presence of the corresponding input character grid can be identified by checking whether a single pixel is black. `
N' should be printed otherwise. (Note that sometimes if a
single pixel is empty, the presence of a character can certainly be
detected. But we are not considering that issue in this problem)
3 2
ABC
...............***.........................
..............*****........................
.............*******.......................
............*********......................
...........***********.....................
..........*************....................
.........*******.*******...................
........*******...*******..................
.......*******.....*******.................
......*********************................
.....***********************...............
....*************************..............
...*******.............*******.............
..*******...............*******............
.*******.................*******...........
*******...................*******..........
...........................................
*****************..........................
******************.........................
*******************........................
********.....*******.......................
..******.....*******.......................
..******.....*******.......................
..*****************........................
..****************.........................
..*****************........................
..******.....*******.......................
..******.....*******.......................
..******.....*******.......................
********************.......................
*******************........................
******************.........................
*****************..........................
...........................................
........*************......................
.....****************......................
...******************......................
..*******************......................
.*******.......******......................
*******....................................
*******....................................
*******....................................
*******....................................
*******....................................
*******....................................
.*******.......******......................
..*******************......................
...******************......................
.....****************......................
........*************......................
...........................................
ABC
AB
Query 1: YYY
Query 2: YY
題目描述：
每個字元圖形都用 16*43 pixel 表示。
輸入只有一組測資，會給定所有字元的表示。
接著會詢問，如果將這幾個字元(這些字元不會重複，且一定在給定的字元中)重疊後，
能不能將每個字元解析出來？
題目解法：
解析出來的定義為，能不能藉由一個 pixel 得到該字元存在重疊的圖形中。
也就是將每個字元貼上計數，看有沒有存在某一格只出現過一次字元。
#include <stdio.h>
#include <string.h>
char pic[40][17][50];
int main() {
int n, q, cases = 0;
int i, j, k;
char s[40];
int mapped[128] = {};
scanf("%d %d", &n, &q);
while(getchar() != '\n');
gets(s);
for(i = 0; s[i]; i++)
mapped[s[i]] = i;
for(i = 0; i < n; i++) {
for(j = 0; j < 17; j++)
gets(pic[i][j]);
}
int g[16][43], used[16][43];
while(q--) {
gets(s);
memset(g, 0, sizeof(g));
for(i = 0; s[i]; i++) {
int idx = mapped[s[i]];
for(j = 0; j < 16; j++) {
for(k = 0; k < 43; k++) {
if(pic[idx][j][k] == '*') {
g[j][k]++;
used[j][k] = i;
}
}
}
}
int ret[50] = {};
for(i = 0; i < 16; i++) {
for(j = 0; j < 43; j++) {
if(g[i][j] == 1)
ret[used[i][j]] = 1;
}
}
printf("Query %d: ", ++cases);
for(i = 0; s[i]; i++)
putchar(ret[i] ? 'Y' : 'N');
puts("");
}
return 0;
}
文章定位：
