谢尔宾斯基地毯
#1538 : 大礼堂地毯
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi的学校大礼堂的地毯是由很多块N × M大小的基本地毯拼接而成的。例如由2×3的基本地毯
ABC
ABD
拼接而成的大礼堂整片地毯如下：
...
ABCABCABCABCAB
ABDABDABDABDAB
. ABCABCABCABCAB .
. ABDABDABDABDAB .
. ABCABCABCABCAB .
ABDABDABDABDAB
ABCABCABCABCAB
...
由于大礼堂面积非常大，可以认为整片地毯是由基本地毯无限延伸拼接的。
现在给出K张地毯的照片，请你判断哪些照片可能是小Hi学校大礼堂地毯的一部分。不需要考虑旋转照片的方向。
例如
BCA
BDA
BCA
可能是上述地毯的一部分，但
BAC
BAD
不可能是上述地毯的一部分。
输入
第1行包含三个整数，N，M 和 K。
第2~N+1行包含一个N × M的矩阵，代表基本地毯的样式。其中每一个元素都是一个大写字母(A-Z)。
之后是 K 张照片的数据。
每张照片的第一行包含两个整数，H 和 W，代表照片的大小。
以下 H 行包含一个 H × W的矩阵，代表照片中地毯的样式。其中每一个元素都是一个大写字母(A-Z)。
对于80%的数据，1 ≤ N, M ≤ 10, 1 ≤ H, W ≤ 100
对于100%的数据， 1 ≤ N, M ≤ 50, 1 ≤ K ≤ 10, 1 ≤ H ≤ 100, 1 ≤ W ≤ 800。
输出
对于每张照片，输出YES或者NO代表它是否可能是大礼堂地毯的一部分。
样例输入
2 3 3
ABC
ABD
3 3
BCA
BDA
BCA
2 3
BAC
BAD
7 14
ABCABCABCABCAB
ABDABDABDABDAB
ABCABCABCABCAB
ABDABDABDABDAB
ABCABCABCABCAB
ABDABDABDABDAB
ABCABCABCABCAB
样例输出
YES
NO
YES
WA了很久，很容易错的模拟题。关键是要根据大礼堂地毯宽度来扩大调整模板宽度(strcat函数/string拼接)，以及逐行地去比较大礼堂地毯是否基础模板匹配（strstr函数/find与string::npos）
1. C++string拼接find & string::npos实现：------->可以3ms实现
#include <cstdio>
#include <cmath>
#include<algorithm>
#include<iOStream>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
int n, m, q, h, w;
string str[55];
string s1[105], s2[105];
bool is_right(){
for(int i = 0; i < n; i++) s2[i] = str[i];
int len = m;
while(len <= w){
for(int i = 0; i < n; i++) s2[i] += str[i]; //C++string的直接拼接
len += m;
}
int k = 0;
for(; k < n; k++){
if(s2[k].find(s1[0]) != string::npos){
break;
}
}
if(k == n) return false;
for(int i = 0; i < h; i++){ //逐行匹配
if(s2[k].find(s1[i]) != string::npos) k = (k + 1) % n;
else return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false); /*建议做题时用cin / cout 时用这句话关闭与stdin的同步
有这行代码-----> 3s
去掉-这行代码-----> 67s*/
while(cin >> n >> m >> q){
for(int i = 0; i < n; i++)
cin >> str[i];
while(q--){
cin >> h >> w;
for(int i = 0; i < h; i++)
cin >> s1[i];
if(is_right()) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
2.strcpy,strstr函数实现: ------>9ms
C里面的几个字符串函数：
char *strcpy(char* dest, const char *src)：把从src地址开始且含有NULL结束符的字符串复制到以dest开始的地址空间
strstr(str1,str2): 判断字符串str2是否是str1的子串。如果是，则该函数返回str2在str1中首次出现的地址；否则，返回NULL。
extern char *strcat(char *dest, const char *src)：把src所指向的字符串（包括“\0”）复制到dest所指向的字符串后面（删除*dest原来末尾的“\0”）。要保证*dest足够长，以容纳被复制进来的*src。*src中原有的字符不变。返回指向dest的指针。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <queue>
#include <climits>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
static const int MAX_N = 15;
char maps[55][55];
char tar_maps[105][805];
char use_maps[105][905];
int n, m, k;
bool judge(int tar_row, int tar_col) {
for (int i = 0; i < n; ++i) strcpy(use_maps[i], maps[i]);
int len = m;
while (len <= tar_col) {
for (int i = 0; i < n; ++i) strcat(use_maps[i], maps[i]);
len += m;
}
int i = 0;
for (; i < n; ++i) {
if (strstr(use_maps[i], tar_maps[0])) {
break;
}
}
if (i == n) return false;
++i;
if (i == n) i = 0;
for (int j = 1; j < tar_row; ++j) {
if (!strstr(use_maps[i], tar_maps[j])) return false;
++i;
if (i == n) i = 0;
}
return true;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i) scanf("%s", maps[i]);
while (k--) {
int h, w;
scanf("%d%d", &h, &w);
for (int i = 0; i < h; ++i) scanf("%s", tar_maps[i]);
if (judge(h, w)) printf("YES\n");
else printf("NO\n");
}
return 0;
}