Advertisement
Guest User

Untitled

a guest
May 28th, 2015
251
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <cstdio>
  2. #define MAXN 300+10
  3. char dmap[MAXN][MAXN],dbmap[20][20];
  4. int n,m,q,a,b,map[MAXN][MAXN],bmap[20],dpmap[MAXN][20];
  5. int main()
  6. {
  7.     int bit,k,found=0,loop;
  8.     scanf("%d%d",&m,&n);
  9.     for (int i = 1; i <= n; ++i)
  10.         scanf("%s",dmap[i]);
  11.     for(int i=1; i<=n; i++)
  12.     {
  13.         for(int j=1; j<=m; j++)
  14.         {
  15.             if(j<=15)
  16.                 dpmap[i][j]=dpmap[i][j-1]+((1<<(j-1))*(dmap[i][j-1]-'A'));
  17.             else
  18.                 dpmap[i][j]=(dpmap[i][j-1]>>1)+((1<<14)*(dmap[i][j-1]-'A'));
  19.         }
  20.     }
  21.   //  printf("%d %d ",dpmap[1][15],dpmap[1][16]);
  22.     /*for(int i=1;i<=n;i++)
  23.     {
  24.         for(int j=1;j<=m;j++)
  25.             printf("%d ",dpmap[i][j]);
  26.         printf("\n");
  27.     }*/
  28.     scanf("%d",&q);
  29.     while(q--)
  30.     {
  31.         found=0;
  32.         scanf("%d%d",&b,&a);
  33.         for(int i=0; i<20; i++)
  34.             bmap[i]=0;
  35.         for (int j = 1; j <= a; ++j)
  36.             scanf("%s",dbmap[j]);
  37.         for (int i = 1; i <= a; ++i){
  38.             for (int j = 0; j < b; ++j)
  39.                 bmap[i]+=(1<<j)*(dbmap[i][j]-'A');
  40.         }
  41.         loop=n-a+1;
  42.         for(int i=1; i<=loop &&found==0; i++)
  43.         {
  44.             for(int j=b; j<=m; j++)
  45.             {
  46.                 if(j<=15)  bit=j-b;
  47.                 else bit=15-b;
  48.                 k=0;
  49.                 if(dpmap[i][j]>>bit==bmap[1])
  50.                 {
  51.                     for(k=1; k<a; k++)
  52.                     {
  53.                         if(dpmap[i+k][j]>>bit!=bmap[k+1])
  54.                             break;
  55.                     }
  56.                 }
  57.                 if(k==a){
  58.                     printf("%d %d\n",((j-b+1)+j)/2,(i+i+a)/2);
  59.                     break;
  60.                     found=1;
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     return 0;
  66. }
  67. /*10 5
  68. ABABABABAB
  69. AAAAABBBBB
  70. AAABBBAAAB
  71. AABBAABBAA
  72. ABBABAABBA
  73. 3
  74. 3 3
  75. BBB
  76. BAA
  77. ABB
  78. 9 3
  79. ABABABABA
  80. AAAAABBBB
  81. AAABBBAAA
  82. 5 1
  83. BBBBB
  84. 16 1
  85. BBBBBBBBBBBBBBBA
  86. 1
  87. 3 1
  88. BBA
  89. 7 1
  90. AABAAAB
  91. 1
  92. 3 1
  93. AAB*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement