https://www.acmicpc.net/problem/3057
3057번: 디버그
상근이는 프로그램을 디버깅할 때, 버그와 프로그램 메모리에서 정사각형 킬러가 깊은 관계가 있다는 것을 알게 되었다. 프로그램 메모리는 1과 0으로만 이루어진 R행 C열 행렬로 이루어져 있다.
www.acmicpc.net
중심점을 기준으로 테두리가 점대칭인지를 검사하는 방식으로 하면 O(N ^ 4)가 된다.
정해는 모든 (x, y)에 대해 그 좌표에서 시작하는 4방향의 2진수 숫자들을 int64나 int32로 전처리 하는 것이라고 한다.
나는 못풀어서 정해대로 풀었는데 O(N ^ 4)로도 뚫린다고 한다.
코드
더보기
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define _unique(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
const int INF = 2e9;
const ll mod = 998244353;
const double eps = 1e-9;
int n, m;
void solve() {
cin>>n>>m;
char board[305][305];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>board[i][j];
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
ll mask[305][305][4] = {0,};
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
for(int a=0;a<2;a++){
int pi = i+dx[a];
int pj = j+dy[a];
mask[i][j][a] = mask[pi][pj][a]<<1;
mask[i][j][a]|=(board[i][j]=='1');
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int a=2;a<4;a++){
int pi = i+dx[a];
int pj = j+dy[a];
mask[i][j][a] = mask[pi][pj][a]<<1;
mask[i][j][a]|=(board[i][j]=='1');
}
}
}
int ans = -1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=300;k++){
if(i-k<1||i+k>n||j-k<1||j+k>m) break;
int sz = k*2+1;
bool chk = true;
int i1 = i-k, j1 = j-k;
int i2 = i+k, j2 = j+k;
while(sz){
if(sz>64){
if(mask[i1][j1][0]!=mask[i2][j2][2]){
chk = false;
break;
}
}
else{
if((mask[i1][j1][0]^mask[i2][j2][2])&((1ll<<sz)-1)){
chk = false;
break;
}
}
int tmp = min(sz, 64);
i1+=tmp;
i2-=tmp;
sz-=tmp;
}
sz = k*2+1;
i1 = i-k, j1 = j-k;
i2 = i+k, j2 = j+k;
while(sz){
if(sz>64){
if(mask[i1][j1][1]!=mask[i2][j2][3]){
chk = false;
break;
}
}
else{
if((mask[i1][j1][1]^mask[i2][j2][3])&((1ll<<sz)-1)){
chk = false;
break;
}
}
int tmp = min(sz, 64);
j1+=tmp;
j2-=tmp;
sz-=tmp;
}
if(chk) ans = max(ans, k*2+1);
else break;
}
}
}
for(int i=1;i<=n-1;i++){
for(int j=1;j<=m-1;j++){
for(int k=0;k<=300;k++){
if(i-k<1||i+k+1>n||j-k<1||j+k+1>m) break;
int sz = k*2+2;
bool chk = true;
int i1 = i-k, j1 = j-k;
int i2 = i+k+1, j2 = j+k+1;
while(sz){
if(sz>64){
if(mask[i1][j1][0]!=mask[i2][j2][2]){
chk = false;
break;
}
}
else{
if((mask[i1][j1][0]^mask[i2][j2][2])&((1ll<<sz)-1)){
chk = false;
break;
}
}
int tmp = min(sz, 64);
i1+=tmp;
i2-=tmp;
sz-=tmp;
}
sz = k*2+2;
i1 = i-k, j1 = j-k;
i2 = i+k+1, j2 = j+k+1;
while(sz){
if(sz>64){
if(mask[i1][j1][1]!=mask[i2][j2][3]){
chk = false;
break;
}
}
else{
if((mask[i1][j1][1]^mask[i2][j2][3])&((1ll<<sz)-1)){
chk = false;
break;
}
}
int tmp = min(sz, 64);
j1+=tmp;
j2-=tmp;
sz-=tmp;
}
if(chk) ans = max(ans, k*2+2);
else break;
}
}
}
cout<<ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
cout.precision(10);
#ifndef ONLINE_JUDGE
freopen("./input.txt", "r", stdin);
clock_t _st_t = clock();
#endif
int tt = 1;
//cin>>tt;
while(tt--){
solve();
cout<<'\n';
}
#ifndef ONLINE_JUDGE
cerr << endl << endl << (double) (clock() - _st_t) / (double) CLOCKS_PER_SEC << "sec" << endl;
#endif
return 0;
}