首页 > 代码库 > [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(状态压缩,枚举,暴力)