记录编号	140708	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014PJ]子矩阵	最终得分	100
用户昵称	albertxwz	是否通过	通过
代码语言	Pascal	运行时间	1.040 s
提交时间	2014-11-24 13:35:28	内存使用	0.17 MiB

var
        mat:array[0..16,0..16] of longint;
        line:array[0..16] of longint;
        n,m,r,c,i,j,min:longint;

procedure dp;
var
        sl:array[1..16] of longint;
	f:array[1..16,1..16] of longint;
        i,j,k,l,sum,minsum:longint;
begin
        fillchar(sl,sizeof(sl),0);
        fillchar(f,sizeof(f),0);
        for i:=1 to m do
                for j:=2 to r do
                        sl[i]:=sl[i]+abs(mat[line[j-1],i]-mat[line[j],i]);
       for i:=1 to m-c+1 do f[1,i]:=sl[i];
        for i:=2 to c do
                for j:=i to m-c+i do
                begin
                        minsum:=maxlongint;
                        for k:=i-1 to j-1 do
                        begin
                                sum:=sl[j];
                                for l:=1 to r do sum:=sum+abs(mat[line[l],k]-mat[line[l],j]);
                                if sum+f[i-1,k]<minsum then minsum:=sum+f[i-1,k];
                        end;
                        f[i,j]:=minsum;
                end;
        for i:=c to m do if min>f[c,i] then min:=f[c,i];
        //if min>f[m] then min:=f[m];
end;

procedure dfs(i:longint);
var
        j:longint;
begin
        if i=r+1 then
        begin
                dp;
                exit;
        end;
        for j:=line[i-1]+1 to n-r+i do
        begin
                line[i]:=j;
                dfs(i+1);
        end;
end;

begin
        //assign(input,'in.txt'); reset(input);
        assign(input,'submatrix.in'); reset(input);
        assign(output,'submatrix.out'); rewrite(output);
        readln(n,m,r,c);
        fillchar(mat,sizeof(mat),0);
        for i:=1 to n do
                for j:=1 to m do
                        read(mat[i,j]);
        line[0]:=0;
        min:=maxlongint;
        dfs(1);
        writeln(min);
        close(input);
        close(output);
end.