#include <bits/stdc++.h>
using namespace std;
const int N=405;
const int inf=1e9+7;
char mat[N][N];
int NS[N][N],ZS[N][N];
int GetN(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];}
int GetZ(int xl, int xr, int yl, int yr){ return ZS[xr][yr]-ZS[xl-1][yr]-ZS[xr][yl-1]+ZS[xl-1][yl-1];}
int SZ(int xl, int xr, int yl, int yr){ return (xr-xl+1)*(yr-yl+1);}
int ans[N][N];
int main()
{
int n,m;
scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&mat[i][j]);
NS[i][j]=NS[i-1][j]+NS[i][j-1]-NS[i-1][j-1]+(mat[i][j]=='N');
ZS[i][j]=ZS[i-1][j]+ZS[i][j-1]-ZS[i-1][j-1]+(mat[i][j]=='Z');
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans[i][j]=inf;
int up=0;
for(int i=0;i<n;i++)
{
if(i>0)
{
int L=0,R=m+1;
while(mat[i][L+1]=='Z') L++;
while(mat[i][R-1]=='N') R--;
if(L+1!=R) break;
up+=m;
}
for(int x=i+1;x<=n;x++) for(int y=1;y<=m;y++)
{
if(GetZ(i+1,x,y,m)==0) ans[x][y]=min(ans[x][y],up+SZ(i+1,x,y,m));
if(GetN(i+1,x,1,y)==0) ans[x][y]=min(ans[x][y],up+SZ(i+1,x,1,y));
}
}
int dw=0;
for(int i=n+1;i>=2;i--)
{
if(i<=n)
{
int L=0,R=m+1;
while(mat[i][L+1]=='N') L++;
while(mat[i][R-1]=='Z') R--;
if(L+1!=R) break;
dw+=m;
}
for(int x=1;x<i;x++) for(int y=1;y<=m;y++)
{
if(GetN(x,i-1,y,m)==0) ans[x][y]=min(ans[x][y],dw+SZ(x,i-1,y,m));
if(GetZ(x,i-1,1,y)==0) ans[x][y]=min(ans[x][y],dw+SZ(x,i-1,1,y));
}
}
int le=0;
for(int j=0;j<m;j++)
{
if(j>0)
{
int L=0,R=n+1;
while(mat[L+1][j]=='Z') L++;
while(mat[R-1][j]=='N') R--;
if(L+1!=R) break;
le+=n;
}
for(int x=1;x<=n;x++) for(int y=j+1;y<=m;y++)
{
if(GetN(1,x,j+1,y)==0) ans[x][y]=min(ans[x][y],le+SZ(1,x,j+1,y));
if(GetZ(x,n,j+1,y)==0) ans[x][y]=min(ans[x][y],le+SZ(x,n,j+1,y));
}
}
int ri=0;
for(int j=m+1;j>=2;j--)
{
if(j<=m)
{
int L=0,R=n+1;
while(mat[L+1][j]=='N') L++;
while(mat[R-1][j]=='Z') R--;
if(L+1!=R) break;
ri+=n;
}
for(int x=1;x<=n;x++) for(int y=1;y<j;y++)
{
if(GetZ(1,x,y,j-1)==0) ans[x][y]=min(ans[x][y],ri+SZ(1,x,y,j-1));
if(GetN(x,n,y,j-1)==0) ans[x][y]=min(ans[x][y],ri+SZ(x,n,y,j-1));
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ans[i][j]==inf) printf("-1 ");
else printf("%i ",ans[i][j]*2);
}
printf("\n");
}
return 0;
}
Compilation message
sandwich.cpp: In function 'int main()':
sandwich.cpp:14: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:19:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&mat[i][j]);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 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 |
3 ms |
660 KB |
Output is correct |
| 7 |
Incorrect |
3 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 |
376 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 |
3 ms |
660 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
