首页 > 代码库 > [POJ3600]Subimage Recognition(状态压缩,枚举,暴力)
[POJ3600]Subimage Recognition(状态压缩,枚举,暴力)
题目链接:http://poj.org/problem?id=3600
枚举行,判断列是否相同。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset>10 #include <vector>11 #include <deque>12 #include <queue>13 #include <stack>14 #include <ctime>15 #include <set>16 #include <map>17 #include <cmath>18 using namespace std;19 20 const int maxn = 22;21 int r, c, R, C;22 char A[maxn][maxn], B[maxn][maxn];23 char tmp[maxn][maxn];24 25 bool check(int sta) {26 memset(tmp, 0, sizeof(tmp));27 int n = 0;28 for(int i = 0; i < R; i++) {29 if((1 << i) & sta) strcpy(tmp[n++], B[i]);30 }31 int cur = 0;32 for(int j = 0; j < C; j++) {33 if(cur >= c) break;34 bool flag = 0;35 for(int i = 0, k = 0; i < n, k < r; i++, k++) {36 if(flag) break;37 if(A[k][cur] != tmp[i][j]) flag = 1;38 }39 if(!flag) cur++;40 }41 return cur >= c;42 }43 44 int main() {45 // freopen("in", "r", stdin);46 scanf("%d%d",&r,&c);47 for(int i = 0; i < r; i++) scanf("%s", A[i]);48 scanf("%d%d",&R,&C);49 for(int i = 0; i < R; i++) scanf("%s", B[i]);50 int RR = 1 << R;51 bool flag = 0;52 for(int i = 0; i < RR; i++) {53 if(check(i)) {54 flag = 1;55 break;56 }57 }58 printf("%s\n", flag?"Yes":"No");59 return 0;60 }
[POJ3600]Subimage Recognition(状态压缩,枚举,暴力)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。