NKPATH – spoj

Đề bài:


Thuật toán:


Với mỗi ô (i,j) với  $i=1..m; j=1..n-1;$ kiểm tra xem ô (ii,jj) với $ii=1..i-1; jj=1..j;$ có đi được đến ô (i,j) không

  • Nếu có
    l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
    

Kết quả: $\sum_{i=1}^{m}L[i][n]$

Code:


const   fi='';
        fo='';
        maxn=100;
        base=1000000000;
type    arra=array[1..maxn,1..maxn] of integer;
        arrl=array[1..maxn,1..maxn] of longint;
var     a:arra;
        i,j,m,n:byte;
        l:arrl;
        f:text;
        res:int64;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,m,n);
    for i:=1 to m do
        for j:=1 to n do read(f,a[i,j]);
    close(f);
end;
procedure init;
begin
    for i:=1 to m do l[i,1]:=1;
 
    res:=0;
end;
function kt(x,y:longint):boolean;
var     tmp:longint;
begin
        while y>0 do
        begin
            x:=x mod y;
            tmp:=x;
            x:=y;
            y:=tmp;
        end;
        if x=1 then exit(false) else exit(true);
end;
procedure xuly;
var     ii,jj:byte;
begin
    for i:=1 to m do
        for j:=1 to n-1 do
        begin
            for ii:=i-1 downto 1 do
                for jj:=j downto 1 do
                        if kt(a[i,j],a[ii,jj]) then l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
            for jj:=j-1 downto 1 do
                if kt(a[i,j],a[i,jj]) then l[i,j]:=(l[i,j]+l[i,jj]) mod base;
        end;
 
    for i:=1 to m do
        for ii:=i downto 1 do
                for jj:=n-1 downto 1 do
                if kt(a[i,n],a[ii,jj]) then res:=(res+l[ii,jj]) mod base;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    xuat;
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

*