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.
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