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