QUEENNB – SPOJ

Đề bài: http://vn.spoj.com/problems/QUEENNB/

Thuật toán:

  • Thuật toán cũng không có gì phức tạp. Mình chỉ duyệt 2 lần: lần 1 từ đầu đến cuối bảng, lần 2 từ cuối về đầu bảng
  • Còn mỗi lần duyệt mình làm gì thì các bạn hãy đọc code vì mình viết code rất dễ hiểu

Code:

const   fi='';
        fo='';
        maxn=1000+3;
 
type    arrf    =array[0..maxn,0..maxn] of longint;
 
var     f       :arrf;
        h,c,d,d2   :arrf;
        i,j,n,m :longint;
        a       :array[1..maxn,1..maxn] of byte;
 
procedure enter;
var     tam     :char;
begin
        assign(input,fi);reset(input);
        readln(m,n);
        for i:=1 to m do
        begin
                for j:=1 to n do
                        begin
                                read(tam);
                                if tam='.' then a[i,j] := 1 else a[i,j] := 0;
                        end;
                readln;
        end;
        close(input);
end;
 
procedure process;
begin
        for i:=1 to m do
                for j:=1 to n do
                        begin
                                if a[i,j]=0 then
                                        begin
                                                h[i,j]:=0;
                                                c[i,j]:=0;
                                                d[i,j]:=0;
                                                d2[i,j] := 0;
                                                continue;
                                        end;
                                h[i,j] := h[i,j-1]+1;
                                c[i,j] := c[i-1,j]+1;
                                d[i,j] := d[i-1,j-1]+1;
                                d2[i,j] := d2[i-1,j+1]+1;
                                f[i,j] := h[i,j]+c[i,j]+d[i,j]+d2[i,j]-4;
                        end;
        fillchar(h,sizeof(h),0);
        fillchar(c,sizeof(c),0);
        fillchar(d,sizeof(d),0);
        fillchar(d2,sizeof(d2),0);
        for i:=m downto 1 do
                for j:=n downto 1 do
                        begin
                                if a[i,j]=0 then
                                        begin
                                                h[i,j] := 0;
                                                c[i,j] := 0;
                                                d[i,j] := 0;
                                                d2[i,j] := 0;
                                                continue;
                                        end;
                                h[i,j] := h[i,j+1]+1;
                                c[i,j] := c[i+1,j]+1;
                                d[i,j] := d[i+1,j+1]+1;
                                d2[i,j] := d2[i+1,j-1]+1;
                                inc(f[i,j] , h[i,j]+c[i,j]+d[i,j]+d2[i,j]-3 );
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        for i:=1 to m do
        begin
                for j:= 1 to n do
                        write(f[i,j],' ');
                writeln;
        end;
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*