## Editorial for Queens

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của happyboy99x

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1000;
int leftToRight[N][N], rightToLeft[N][N];
int topToBottom[N][N], bottomToTop[N][N];;
int topLeftToBottomRight[N][N], bottomRightToTopLeft[N][N];
int topRightToBottomLeft[N][N], bottomLeftToTopRight[N][N];
int m, n;
string s[N];

bool valid(int x, int y) {
return 0 <= x && x < m && 0 <= y && y < n;
}

void go(int sx, int sy, int dx, int dy, int a[][N]) {
for(int x = sx, y = sy, curr = 0; valid(x, y); x += dx, y += dy) {
if(s[x][y] == '#') curr = -1;
a[x][y] = curr++;
}
}

int main() {
ios::sync_with_stdio(false);
cin >> m >> n;
for(int i = 0; i < m; ++i)
cin >> s[i];
for(int j = 0; j < n; ++j) {
go(0, j, 1, 0, topToBottom);
go(0, j, 1, 1, topLeftToBottomRight);
go(0, j, 1, -1, topRightToBottomLeft);
go(m - 1, j, -1, 0, bottomToTop);
go(m - 1, j, -1, 1, bottomLeftToTopRight);
go(m - 1, j, -1, -1, bottomRightToTopLeft);
}
for(int i = 0; i < m; ++i) {
go(i, 0, 0, 1, leftToRight);
go(i, 0, 1, 1, topLeftToBottomRight);
go(i, 0, -1, 1, bottomLeftToTopRight);
go(i, n - 1, 0, -1, rightToLeft);
go(i, n - 1, 1, -1, topRightToBottomLeft);
go(i, n - 1, -1, -1, bottomRightToTopLeft);
}
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j) {
if(s[i][j] == '#') printf("0");
else printf("%d", topToBottom[i][j] + bottomToTop[i][j]
+ leftToRight[i][j] + rightToLeft[i][j]
+ topLeftToBottomRight[i][j] + topRightToBottomLeft[i][j]
+ bottomLeftToTopRight[i][j] + bottomRightToTopLeft[i][j] + 1);
if(j + 1 == n) printf("\n");
else printf(" ");
}
return 0;
}


program queennb;
uses    math;
const   maxN=1111;
fi='';
var     a,f:array[1..maxN,1..maxN] of longint;
m,n:longint;
procedure input;
var     inp:text;
c:char;
i,j:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to m do
begin
for j:=1 to n do
begin
if c='#' then
a[i,j]:=1
else
a[i,j]:=0;

end;
end;
close(inp);
end;

procedure init;
var     i,j:longint;
begin
for i:=1 to m do
for j:=1 to n do
if a[i,j]=0 then
f[i,j]:=1;
end;

procedure inc2(var  x,y:longint);
begin
inc(x);
inc(y);
end;

procedure processDown;
var     i,j,k,t:longint;
begin
for j:=1 to n do
begin
i:=1;
while i<=m do
begin
while (i<=m) and (a[i,j]=1) do inc(i);
k:=i;
while (k<=m) and (a[k,j]=0) do inc(k);
for t:=i to k-1 do
inc(f[t,j],k-i-1);
i:=k+1;
end;
end;
end;

procedure processRight;
var     i,j,k,t:longint;
begin
for i:=1 to m do
begin
j:=1;
while j<=n do
begin
while (j<=n) and (a[i,j]=1) do inc(j);
k:=j;
while (k<=n) and (a[i,k]=0) do inc(k);
for t:=j to k-1 do
inc(f[i,t],k-j-1);
j:=k+1;
end;
end;
end;

procedure processCrossLR;
var     row,col,i,j,ki,kj,t,x:longint;
begin
for row:=1 to m do
begin
i:=row;
j:=1;
while (i<=m) and (j<=n) do
begin
while (i<=m) and (j<=n) and (a[i,j]=1) do inc2(i,j);
ki:=i;kj:=j;
while (ki<=m) and (kj<=n) and (a[ki,kj]=0) do inc2(ki,kj);
x:=ki-i;
t:=x;
while t>0 do
begin
inc(f[i,j],x-1);
inc2(i,j);
dec(t);
end;
inc2(i,j);
end;
end;
for col:=2 to n do
begin
i:=1;
j:=col;
while (i<=m) and (j<=n) do
begin
while (i<=m) and (j<=n) and (a[i,j]=1) do inc2(i,j);
ki:=i;kj:=j;
while (ki<=m) and (kj<=n) and (a[ki,kj]=0) do inc2(ki,kj);
x:=ki-i;
t:=x;
while t>0 do
begin
inc(f[i,j],x-1);
inc2(i,j);
dec(t);
end;
inc2(i,j);
end;
end;

end;

procedure processCrossRL;
var     row,col,i,j,ki,kj,t,x:longint;
begin
for row:=m downto 1 do
begin
i:=row;
j:=1;
while (i>=1) and (j<=n) do
begin
while (i>=1) and (j<=n) and (a[i,j]=1) do begin dec(i);inc(j);end;
ki:=i;kj:=j;
while (ki>=1) and (kj<=n) and (a[ki,kj]=0) do begin dec(ki);inc(kj);end;
x:=kj-j;
t:=x;
while t>0 do
begin
inc(f[i,j],x-1);
dec(i);inc(j);
dec(t);
end;
dec(i);
inc(j);
end;
end;
for col:=2 to n do
begin
i:=m;
j:=col;
while (i>=1) and (j<=n) do
begin
while (i>=1) and (j<=n) and (a[i,j]=1) do begin dec(i);inc(j);end;
ki:=i;kj:=j;
while (ki>=1) and (kj<=n) and (a[ki,kj]=0) do begin dec(ki);inc(kj);end;
x:=kj-j;
t:=x;
while t>0 do
begin
inc(f[i,j],x-1);
dec(i);inc(j);
dec(t);
end;
dec(i);
inc(j);
end;
end;

end;

procedure output;
var     i,j:longint;
begin
for i:=1 to m do
begin
for j:=1 to n do
write(f[i,j],' ');
writeln;
end;
end;

begin
input;
init;
processDown;
processRight;
processCrossLR;
processCrossRL;
output;
end.


#### Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<vector>
#define MAX   3030
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
char a[MAX][MAX];
int m,n;
vector<int> row[MAX];
vector<int> col[MAX];
vector<int> pdia[MAX];
vector<int> mdia[MAX];
void init(void) {
scanf("%d",&m);
scanf("%d",&n);
FOR(i,1,m) scanf("%s",a[i]+1);
FOR(i,0,m+1) {
a[i][0]='#';
a[i][n+1]='#';
}
FOR(i,0,n+1) {
a[0][i]='#';
a[m+1][i]='#';
}
}
void precount(void) {
FOR(i,0,m+1) FOR(j,0,n+1) if (a[i][j]!='.') {
row[i].push_back(j);
col[j].push_back(i);
pdia[i+j].push_back(i);
mdia[i-j+n+1].push_back(i);
}
}
if (a[x][y]!='.') return (0);
int ret=1;
int t;
t=lower_bound(row[x].begin(),row[x].end(),y)-row[x].begin();
ret+=row[x][t]-row[x][t-1]-2;
t=lower_bound(col[y].begin(),col[y].end(),x)-col[y].begin();
ret+=col[y][t]-col[y][t-1]-2;
t=lower_bound(pdia[x+y].begin(),pdia[x+y].end(),x)-pdia[x+y].begin();
ret+=pdia[x+y][t]-pdia[x+y][t-1]-2;
t=lower_bound(mdia[x-y+n+1].begin(),mdia[x-y+n+1].end(),x)-mdia[x-y+n+1].begin();
ret+=mdia[x-y+n+1][t]-mdia[x-y+n+1][t-1]-2;
return (ret);
}
void process(void) {
FOR(i,1,m) FOR (j,1,n){
if (j<n) printf(" ");
else printf("\n");
}
}
int main(void) {
//freopen("QUEEN.INP","r",stdin);
//freopen("QUEEN.OUT","w",stdout);
init();
precount();
process();
return 0;
}