#include <bits/stdc++.h>
using namespace std;
const int N=405;
const int inf=1e9+7;
char mat[N][N],tmp1[N][N];
int n,m,id[N][N],tmp2[N][N],ans[N*N];
void rot()
{
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
tmp1[m-j+1][i]=mat[i][j];
tmp2[m-j+1][i]=id[i][j];
}
swap(n,m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
mat[i][j]=tmp1[i][j];
if(mat[i][j]=='N') mat[i][j]='Z';
else mat[i][j]='N';
id[i][j]=tmp2[i][j];
}
}
bool dp[N][N];
int NS[N][N];
int Get(int xl, int xr, int yl, int yr){ return NS[xr][yr]-NS[xl-1][yr]-NS[xr][yl-1]+NS[xl-1][yl-1];}
void Solve()
{
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) NS[i][j]=NS[i-1][j]+NS[i][j-1]-NS[i-1][j-1]+(mat[i][j]=='N');
dp[1][1]=1;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(i!=1 || j!=1)
{
dp[i][j]=0;
if(i!=1 && dp[i-1][j])
{
int L=j-1,R=m+1;
while(L<m && mat[i-1][L+1]=='Z') L++;
while(R>j && mat[i-1][R-1]=='N') R--;
if(L+1==R) dp[i][j]=1;
}
if(j!=1 && dp[i][j-1])
{
int L=i-1,R=n+1;
while(L<n && mat[L+1][j-1]=='Z') L++;
while(R>i && mat[R-1][j-1]=='N') R--;
if(L+1==R) dp[i][j]=1;
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
for(int k=j;k>=1;k--)
{
int bot=1,top=i,mid,sol=-1;
while(top>=bot)
{
mid=top+bot>>1;
if(Get(mid,i,k,j)==0) sol=mid,top=mid-1;
else bot=mid+1;
}
if(sol!=-1 && dp[sol][k]) ans[id[i][j]]=min(ans[id[i][j]],(j-k+1)*(i-sol+1)+n*(k-1)+m*(sol-1)-(k-1)*(sol-1));
}
}
}
int main()
{
scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j]=(i-1)*m+j;
for(int i=1;i<=n*m;i++) ans[i]=inf;
for(int i=1;i<=n;i++) scanf("%s",mat[i]+1);
for(int i=1;i<=4;i++) Solve(),rot();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ans[(i-1)*m+j]==inf) printf("-1 ");
else printf("%i ",ans[(i-1)*m+j]*2);
}
printf("\n");
}
return 0;
}
Compilation message
sandwich.cpp: In function 'void Solve()':
sandwich.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=top+bot>>1;
~~~^~~~
sandwich.cpp: In function 'int main()':
sandwich.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
sandwich.cpp:68:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%s",mat[i]+1);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
6 ms |
636 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
632 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
6 ms |
636 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
632 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
