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;
}

Code mẫu của ladpro98

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);
        readln(inp,m,n);
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                read(inp,c);
                if c='#' then
                a[i,j]:=1
                else
                a[i,j]:=0;

                end;
                readln(inp);
        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);
    }   
}
int answer(int x,int y) {
    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){
        printf("%d",answer(i,j));
        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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.