Polyomino Composer（搜索）
A polyomino is a plane geometric figure formed by joining one or more equal squares edge
to edge.
·········································································································– Wikipedia
Given a large polyomino and a small polyomino, your task is to determine whether you can compose
the large one with two copies of the small one. The polyominoes can be translated, but not flipped or
rotated. The two pieces should not overlap. The leftmost picture below is a correct way of composing
the large polyomino, but the right two pictures are not. In the middle picture, one of the pieces was
rotated. In the rightmost picture, both pieces are exactly identical, but they’re both rotated from the
original piece (shown in the lower-right part of the picture).
Input
There will be at most 20 test cases. Each test case begins with two integers n and m (1 ≤ m ≤ n ≤ 10)
in a single line. The next n lines describe the large polyomino. Each of these lines contains exactly n
characters in ‘’,‘.’. A ‘’ indicates an existing square, and a ‘.’ indicates an empty square. The next
m lines describe the small polyomino, in the same format. These characters are guaranteed to form
valid polyominoes (note that a polyomino contains at least one existing square). The input terminates
with n = m = 0, which should not be processed.
Output
For each case, print ‘1’ if the corresponding composing is possible, print ‘0’ otherwise.
Sample Input
Sample Output
1
0
0
本题题意大概就是说，先输入n行字符串，表示用polyomino这种图形拼接成的大图形，再输入m行字符串，表示polyomino这个图形。其中，n行字符串表示的大图形可以由若干个polyomino图形表示，其中polyomino图形拼接时，可以平移，但不可以改变图形的形状也不可以将polyomino图形旋转。
最终判断n行字符串组成的大图形，是否能用若干个polyomino图形构成，若可以，则输出1，反之，输出0.
本题的思路也很简单，因为数据量不大，仅仅使用for循环即可过题。
- 首先，我们将n行字符串和m行字符串分别存入数组中。
- 其次，我们将m行字符串的位置记录下来， polyomino图形的每个‘ * ’位置，用前一个‘ * ’位置表示出来，具体表示方式请看代码中的map数组。
- 运用for循环，查找n行字符串中，带有’ * '的位置，然后进入对比，是否能用polyomino图形将其重合消去。
- 若都能消去，输出1，反之输出0.
本题一开始使用了比较复杂的写法，后来发现若能用polyomino图形消去，即任何位置都能满足，否则，不论如何消去，都无法满足题意。先贴出复杂代码，再贴出简单代码。2个代码都能AC题目。
/*复杂代码*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
int n, m;
while (cin >> n >> m && n && m)
{
char a[150][150];
char b[150][150];
int map[100005];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
int p = 0;
int x = 0, y = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j<m; j++)
{
if (b[i][j] == '*')
{
map[p++] = i - x;
map[p++] = j - y;
x = i;
y = j;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j<n; j++)
{
if (a[i][j] == '*')
{
a[i][j] = '.';
int l = i, r = j;
for (int ii = 2; ii < p; ii = ii + 2)
{
l = l + map[ii];
r = r + map[ii + 1];
if (a[l][r] == '*')
{
a[l][r] = '.';
}
else
{
for (; ii >= 2; ii = ii - 2)
{
l = l - map[ii];
r = r - map[ii + 1];
a[l][r] = '*';
}
break;
}
}
}
}
}
int flag = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j<n; j++)
{
if (a[i][j] == '*')
{
flag = 1;
break;
}
}
}
if (flag==1)
cout << "0" << endl;
else
cout << "1" << endl;
}
return 0;
}
/*稍微简单一点代码*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
char a[15][15];
char b[15][15];
int map[105];
int n, m;
int main()
{
while (cin >> n >> m && n && m)
{
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
int p = 0;
int x = 0, y = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; a[i][j] != ' '; j++)
{
if (b[i][j] == '*')
{
map[p++] = i - x;
map[p++] = j - y;
x = i;
y = j;
}
}
}
int flag = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j<n; j++)
{
if (a[i][j] == '*' && flag == 0)
{
a[i][j] = '.';
int l = i, r = j;
for (int ii = 2; ii < p; ii = ii + 2)
{
l = l + map[ii];
r = r + map[ii + 1];
if (a[l][r] == '*')
{
a[l][r] = '.';
}
else
{
//cout << a[l][r] << endl;
//cout << l << " "<<r << endl;
flag = 1;
break;
}
}
}
if (flag == 1)
break;
}
}
if (flag == 1)
cout << "0" << endl;
else
cout << "1" << endl;
}
return 0;
}
Comments NOTHING