| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
终于AC了,在TLE12次后。。位运算+暴力匹配。。注意一下这个TLE的点。。直接上我的AC代码。注意一下在judge里面的那个注释。。
[code=C/C++]
// Oh,my god!! &%$%@#$$%#%&@#%&&......
// TLE,TLE,TLE... TLE*12,WA*3......
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int m,n,p,q;
char map[1010][1010],star[55][55];
long long int mapnum[1010][1010],starnum[55];
bool judge()
{
bool e;
/*** If you swap the "for" of i and j here,then you will TLE.......... ***/
for (int i=0;i<=m-p;i++)
{
for (int j=0;j<=n-q;j++)
{
e=true;
for (int w=0;w<=p-1;w++)
{
if (mapnum[i+w][j]!=starnum[w])
{
e=false;break;
}
}
if (e) return true;
}
}
return false;
}
int main()
{
int t=0,k,num=0;
long long int flag;
while (cin >> m >> n >> k >> p >> q)
{
if (m+n+k+p+q==0) break;
t++;num=0;
flag=~(1LL<<(q-1));
if (p>m || q>n)
{
printf("Case %d: 0\n",t);continue;
}
for (int i=0;i<=m-1;i++)
{
mapnum[i][0]=0;
scanf("%s",map[i]);
for (int j=0;j<=q-1;j++)
{
mapnum[i][0]<<=1;
mapnum[i][0]|=(map[i][j]=='*');
}
for (int j=1;j<=n-q;j++)
mapnum[i][j]=((mapnum[i][j-1]&flag)<<1)|(map[i][j+q-1]=='*');
}
while (k--)
{
for (int i=0;i<=p-1;i++)
{
scanf("%s",star[i]);
starnum[i]=0;
for (int j=0;j<=q-1;j++)
{
starnum[i]<<=1;
starnum[i]|=(star[i][j]=='*');
}
}
if (judge())
num++;
}
printf("Case %d: %d\n",t,num);
}
return 0;
}
[/code]
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator