LeetCode Weekly Contest 147
問題文
省略
省略
#include<bits/stdc++.h>
using namespace std;
template<class T> void malloc2d(T ***arr, int x, int y){
int i;
(*arr) = (T**)malloc(x*sizeof(T*));
(*arr)[0] = (T*)malloc(x*y*sizeof(T));
for(i=(1);i<(x);i++){
(*arr)[i]=(*arr)[i-1]+y;
}
}
template<class T> void free2d(T **arr){
free(arr[0]);
free(arr);
}
template<class T> inline T pow2_L(T a){
return a*a;
}
template<class S, class T> inline S chmax(S &a, T b){
if(a<b){
a=b;
}
return a;
}
template<class T> struct Grid2d{
T **d, **d_s;
int c, **dw, **lf, r, **rg, set_d, set_s, **up;
void malloc(const int rr, const int cc){
r = rr;
c = cc;
set_s = 0;
set_d = 0;
malloc2d(&d, r, c);
}
void free(void){
free2d(d);
if(set_s){
free2d(d_s);
}
if(set_d){
free2d(up);
free2d(dw);
free2d(lf);
free2d(rg);
}
}
T*operator[](int a){
return d[a];
}
void setSum(void){
int i, j;
if(set_s == 0){
set_s = 1;
malloc2d(&d_s, r+1, c+1);
}
for(i=0;i<(r+1);i++){
d_s[i][0] = 0;
}
for(j=0;j<(c+1);j++){
d_s[0][j] = 0;
}
for(i=0;i<(r);i++){
for(j=0;j<(c);j++){
d_s[i+1][j+1] = d_s[i][j+1] + d_s[i+1][j] - d_s[i][j] + d[i][j];
}
}
}
void setDir(void){
int i, j;
if(set_d == 0){
set_d = 1;
malloc2d(&up, r, c);
malloc2d(&dw, r, c);
malloc2d(&lf, r, c);
malloc2d(&rg, r, c);
}
for(j=0;j<(c);j++){
up[0][j] = 1;
}
for(i=(1);i<(r);i++){
for(j=0;j<(c);j++){
if(d[i][j]==d[i-1][j]){
up[i][j] = 1 + up[i-1][j];
}
else{
up[i][j] = 1 ;
}
}
}
for(j=0;j<(c);j++){
dw[r-1][j] = 1;
}
for(i=r-2;i>=0;i--){
for(j=0;j<(c);j++){
if(d[i][j]==d[i+1][j]){
dw[i][j] = 1 + dw[i+1][j];
}
else{
dw[i][j] = 1 ;
}
}
}
for(i=0;i<(r);i++){
lf[i][0] = 1;
for(j=(1);j<(c);j++){
if(d[i][j]==d[i][j-1]){
lf[i][j] = 1 + lf[i][j-1];
}
else{
lf[i][j] = 1 ;
}
}
}
for(i=0;i<(r);i++){
rg[i][c-1] = 1;
for(j=c-2;j>=0;j--){
if(d[i][j]==d[i][j+1]){
rg[i][j] = 1 + rg[i][j+1];
}
else{
rg[i][j] = 1 ;
}
}
}
}
void setDirMatch(const T v){
int i, j;
if(set_d == 0){
set_d = 1;
malloc2d(&up, r, c);
malloc2d(&dw, r, c);
malloc2d(&lf, r, c);
malloc2d(&rg, r, c);
}
for(j=0;j<(c);j++){
if(d[0][j]==v){
up[0][j] =1;
}
else{
up[0][j] =0;
}
}
for(i=(1);i<(r);i++){
for(j=0;j<(c);j++){
if(d[i][j]==v){
up[i][j] =1 + up[i-1][j];
}
else{
up[i][j] =0;
}
}
}
for(j=0;j<(c);j++){
if(d[r-1][j]==v){
dw[r-1][j] =1;
}
else{
dw[r-1][j] =0;
}
}
for(i=r-2;i>=0;i--){
for(j=0;j<(c);j++){
if(d[i][j]==v){
dw[i][j] =1 + dw[i+1][j];
}
else{
dw[i][j] =0;
}
}
}
for(i=0;i<(r);i++){
if(d[i][0]==v){
lf[i][0] =1;
}
else{
lf[i][0] =0;
}
for(j=(1);j<(c);j++){
if(d[i][j]==v){
lf[i][j] =1 + lf[i][j-1];
}
else{
lf[i][j] =0;
}
}
}
for(i=0;i<(r);i++){
if(d[i][c-1]==v){
rg[i][c-1] =1;
}
else{
rg[i][c-1] =0;
}
for(j=c-2;j>=0;j--){
if(d[i][j]==v){
rg[i][j] =1 + rg[i][j+1];
}
else{
rg[i][j] =0;
}
}
}
}
T getSum(const int r1, const int c1, const int r2, const int c2){
return d_s[r2+1][c2+1] - d_s[r1][c2+1] - d_s[r2+1][c1] + d_s[r1][c1];
}
}
;
class Solution{
public:
int largest1BorderedSquare(vector<vector<int>>& grid){
Grid2d<int> g;
int X, Y, i, j, k, ni, nj, res=0;
X = grid.size();
Y = grid[0].size();
g.malloc(X, Y);
for(i=0;i<(X);i++){
for(j=0;j<(Y);j++){
g[i][j] = grid[i][j];
}
}
g.setDirMatch(1);
for(i=0;i<(X);i++){
for(j=0;j<(Y);j++){
for(k=0;;k++){
ni = i + k;
nj = j + k;
if(ni >= X || nj >= Y){
break;
}
if(g.rg[i][j] <= k || g.dw[i][j] <= k){
break;
}
if(g.lf[ni][nj] <= k || g.up[ni][nj] <= k){
continue;
}
chmax(res,pow2_L((k+1)));
}
}
}
g.free();
return res;
}
}
;
// cLay varsion 20190802-2
// --- original code ---
// class Solution {
// public:
// int largest1BorderedSquare(vector<vector<int>>& grid) {
// int X, Y;
// Grid2d<int> g;
// int i, j, k, ni, nj;
// int res = 0;
//
// X = grid.size();
// Y = grid[0].size();
// g.malloc(X, Y);
// rep(i,X) rep(j,Y) g[i][j] = grid[i][j];
// g.setDirMatch(1);
//
// rep(i,X) rep(j,Y) for(k=0;;k++){
// ni = i + k;
// nj = j + k;
// if(ni >= X || nj >= Y) break;
// if(g.rg[i][j] <= k || g.dw[i][j] <= k) break;
// if(g.lf[ni][nj] <= k || g.up[ni][nj] <= k) continue;
// res >?= (k+1) ** 2;
// }
//
// g.free();
// return res;
// }
// };
//
// {
// // main関数を適当に処理する
// }
#include<bits/stdc++.h>
using namespace std;
template<class T> void malloc2d(T ***arr, int x, int y){
int i;
(*arr) = (T**)malloc(x*sizeof(T*));
(*arr)[0] = (T*)malloc(x*y*sizeof(T));
for(i=(1);i<(x);i++){
(*arr)[i]=(*arr)[i-1]+y;
}
}
template<class T> void free2d(T **arr){
free(arr[0]);
free(arr);
}
template<class T> inline T pow2_L(T a){
return a*a;
}
template<class S, class T> inline S chmax(S &a, T b){
if(a<b){
a=b;
}
return a;
}
template<class T> struct Grid2d{
T **d, **d_s;
int c, **dw, **lf, r, **rg, set_d, set_s, **up;
void malloc(const int rr, const int cc){
r = rr;
c = cc;
set_s = 0;
set_d = 0;
malloc2d(&d, r, c);
}
void free(void){
free2d(d);
if(set_s){
free2d(d_s);
}
if(set_d){
free2d(up);
free2d(dw);
free2d(lf);
free2d(rg);
}
}
T*operator[](int a){
return d[a];
}
void setSum(void){
int i, j;
if(set_s == 0){
set_s = 1;
malloc2d(&d_s, r+1, c+1);
}
for(i=0;i<(r+1);i++){
d_s[i][0] = 0;
}
for(j=0;j<(c+1);j++){
d_s[0][j] = 0;
}
for(i=0;i<(r);i++){
for(j=0;j<(c);j++){
d_s[i+1][j+1] = d_s[i][j+1] + d_s[i+1][j] - d_s[i][j] + d[i][j];
}
}
}
void setDir(void){
int i, j;
if(set_d == 0){
set_d = 1;
malloc2d(&up, r, c);
malloc2d(&dw, r, c);
malloc2d(&lf, r, c);
malloc2d(&rg, r, c);
}
for(j=0;j<(c);j++){
up[0][j] = 1;
}
for(i=(1);i<(r);i++){
for(j=0;j<(c);j++){
if(d[i][j]==d[i-1][j]){
up[i][j] = 1 + up[i-1][j];
}
else{
up[i][j] = 1 ;
}
}
}
for(j=0;j<(c);j++){
dw[r-1][j] = 1;
}
for(i=r-2;i>=0;i--){
for(j=0;j<(c);j++){
if(d[i][j]==d[i+1][j]){
dw[i][j] = 1 + dw[i+1][j];
}
else{
dw[i][j] = 1 ;
}
}
}
for(i=0;i<(r);i++){
lf[i][0] = 1;
for(j=(1);j<(c);j++){
if(d[i][j]==d[i][j-1]){
lf[i][j] = 1 + lf[i][j-1];
}
else{
lf[i][j] = 1 ;
}
}
}
for(i=0;i<(r);i++){
rg[i][c-1] = 1;
for(j=c-2;j>=0;j--){
if(d[i][j]==d[i][j+1]){
rg[i][j] = 1 + rg[i][j+1];
}
else{
rg[i][j] = 1 ;
}
}
}
}
void setDirMatch(const T v){
int i, j;
if(set_d == 0){
set_d = 1;
malloc2d(&up, r, c);
malloc2d(&dw, r, c);
malloc2d(&lf, r, c);
malloc2d(&rg, r, c);
}
for(j=0;j<(c);j++){
if(d[0][j]==v){
up[0][j] =1;
}
else{
up[0][j] =0;
}
}
for(i=(1);i<(r);i++){
for(j=0;j<(c);j++){
if(d[i][j]==v){
up[i][j] =1 + up[i-1][j];
}
else{
up[i][j] =0;
}
}
}
for(j=0;j<(c);j++){
if(d[r-1][j]==v){
dw[r-1][j] =1;
}
else{
dw[r-1][j] =0;
}
}
for(i=r-2;i>=0;i--){
for(j=0;j<(c);j++){
if(d[i][j]==v){
dw[i][j] =1 + dw[i+1][j];
}
else{
dw[i][j] =0;
}
}
}
for(i=0;i<(r);i++){
if(d[i][0]==v){
lf[i][0] =1;
}
else{
lf[i][0] =0;
}
for(j=(1);j<(c);j++){
if(d[i][j]==v){
lf[i][j] =1 + lf[i][j-1];
}
else{
lf[i][j] =0;
}
}
}
for(i=0;i<(r);i++){
if(d[i][c-1]==v){
rg[i][c-1] =1;
}
else{
rg[i][c-1] =0;
}
for(j=c-2;j>=0;j--){
if(d[i][j]==v){
rg[i][j] =1 + rg[i][j+1];
}
else{
rg[i][j] =0;
}
}
}
}
T getSum(const int r1, const int c1, const int r2, const int c2){
return d_s[r2+1][c2+1] - d_s[r1][c2+1] - d_s[r2+1][c1] + d_s[r1][c1];
}
}
;
class Solution{
public:
int largest1BorderedSquare(vector<vector<int>>& grid){
Grid2d<int> g;
int X, Y, i, j, k, ni, nj, p, res=0;
X = grid.size();
Y = grid[0].size();
g.malloc(X, Y);
for(i=0;i<(X);i++){
for(j=0;j<(Y);j++){
g[i][j] = grid[i][j];
}
}
g.setSum();
for(i=0;i<(X);i++){
for(j=0;j<(Y);j++){
if(g[i][j]==1){
res = 1;
}
}
}
for(i=0;i<(X);i++){
for(j=0;j<(Y);j++){
for(k=1;;k++){
ni = i + k;
nj = j + k;
if(ni >= X || nj >= Y){
break;
}
p = g.getSum(i,j,ni,nj);
if(k>=2){
p -= g.getSum(i+1,j+1,ni-1,nj-1);
}
if(p == 4*k){
chmax(res,pow2_L((k+1)));
}
}
}
}
g.free();
return res;
}
}
;
// cLay varsion 20190802-2
// --- original code ---
// class Solution {
// public:
// int largest1BorderedSquare(vector<vector<int>>& grid) {
// int X, Y;
// Grid2d<int> g;
// int i, j, k, ni, nj, p;
// int res = 0;
//
// X = grid.size();
// Y = grid[0].size();
// g.malloc(X, Y);
// rep(i,X) rep(j,Y) g[i][j] = grid[i][j];
// g.setSum();
//
// rep(i,X) rep(j,Y) if(g[i][j]==1) res = 1;
//
// rep(i,X) rep(j,Y) for(k=1;;k++){
// ni = i + k;
// nj = j + k;
// if(ni >= X || nj >= Y) break;
//
// p = g.getSum(i,j,ni,nj);
// if(k>=2) p -= g.getSum(i+1,j+1,ni-1,nj-1);
//
// if(p == 4k) res >?= (k+1) ** 2;
// }
//
// g.free();
// return res;
// }
// };
//
// {
// // main関数を適当に処理する
// }
Current time: 2024年04月25日22時09分01秒
Last modified: 2019年08月10日16時44分24秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る
Logged in as: unknown user (not login)