Bài toán
Cho một mảng kí tự kích thước m x n. Tìm hình vuông con có kích thước lớn nhất mà có tâm đối xứng (tức là ảnh không bị thay đổi nếu xoay 180 độ). Các kí tự trong mảng luôn là '1' hoặc '0'.
Input
Dòng 1 chứa số nguyên dương m và n (m,n<=300). m dòng tiếp theo mỗi dòng là một chuỗi n kí tự, mỗi kí tự chỉ có thể là 1 hoặc 0.
Output
In ra chiều dài của hình vuông con lớn nhất tìm được. Nếu chiều dài đó nhỏ hơn hoặc bằng 1 thì in ra -1.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <stdlib.h>
typedef int two_dimension[345][345];
bool maximize(int &a, int b){ if ( a<b) a=b; else return false; return true; }
int m, n;
char a[345][345];
int _2309[12309];
two_dimension FWDX, FWDY, BCKX, BCKY;
bool F[345][345][345];
int FF[345][345][345];
int fwdX(int x, int y){
if (x==0) return 0;
if (FWDX[x][y]) return FWDX[x][y];
int r = fwdX(x-1, y)*2309+a[x][y];
return FWDX[x][y]=r;
}
int fwdY(int x, int y){
if (y==0) return 0;
if (FWDY[x][y]) return FWDY[x][y];
int r = fwdY(x, y-1)*2309+a[x][y];
return FWDY[x][y]=r;
}
int bckX(int x, int y){
//printf("bckX(%d, %d) = ?\n", x, y);
if (x==m+1) return 0;
if (BCKX[x][y]) return BCKX[x][y];
int r = bckX(x+1, y)*2309+a[x][y];
//printf("bckX(%d, %d) = %d\n", x, y, r);
return BCKX[x][y]=r;
}
int bckY(int x, int y){
if (y==n+1) return 0;
if (BCKY[x][y]) return BCKY[x][y];
int r = bckY(x,y+1)*2309+a[x][y];
return BCKY[x][y] = r;
}
int fwdX(int A, int y, int B){ return fwdX(B,y)-fwdX(A-1,y)*_2309[B-A+1]; }
int fwdY(int x, int A, int B){ return fwdY(x,B)-fwdY(x,A-1)*_2309[B-A+1]; }
int bckX(int A, int y, int B){ return bckX(B,y)-bckX(A+1,y)*_2309[A-B+1]; }
int bckY(int x, int A, int B){ return bckY(x,B)-bckY(x,A+1)*_2309[A-B+1]; }
bool ok(int k, int x, int y){
if (k==0 || k==1) return true;
if (FF[k][x][y]++) return F[k][x][y];
if (!ok(k-2,x+1,y+1)) return false;
if (fwdX(x+1,y+1,x+k) != bckX(x+k,y+k,x+1)) return F[k][x][y]=false;
if (fwdY(x+1,y+1,y+k) != bckY(x+k,y+k,y+1)) return F[k][x][y]=false;
return F[k][x][y]=true;
}
main(){
int i, j, k, answer=-1;
scanf("%d%d", &m, &n);
for (i=1; i<=m; i++) scanf("%s", a[i]+1);
_2309[0]=1;
for (i=1; i<=m+n; i++) _2309[i]=_2309[i-1]*2309;
for (k=(m>n?n:m); k>=2; k--)
for (i=0; i+k<=m; i++)
for (j=0; j+k<=n; j++)
if (ok(k,i,j)) maximize(answer, k);
printf("%d\n", answer);
}
Nhận xét
Trên máy 2.20GHz, TL 1s, code trên đạt 77 / 100 điểm. Với TL 2s, code trên đạt 100 / 100 điểm. Các bạn có thể tối ưu bằng cách khử đệ quy hàm hash.
Mô tả
fwdx, fwdy, bckx, bcky
4 hàm hash theo 4 hướng khác nhau.
bool ok(int k, int x, int y)
kiểm tra xem hình vuông cạnh x có tọa độ hai đỉnh đối là (x+1, y+1), (x+k, y+k) có tâm đối xứng hay không.