求优化方案或更好的方法

纯暴力,只过一个点...
var map:array[1..10000,1..10000] of char;
data:array[1..10000,1..10000] of longint;
m,n,ans,i,j,max:longint;

procedure init;
var i,j:longint;
begin
readln(m,n);
for i:=1 to m do
for j:=1 to m do
read(map[i,j]);
end;

procedure change;
var i,j:longint;
begin
for i:=1 to m do
for j:=1 to m do
if map[i,j]='.' then
begin
data[i,j]:=0;
end
else data[i,j]:=1;
end;

procedure count(x,y:integer);
var i,j,xn1,xn2,yn1,yn2:longint;
begin
ans:=0;
xn1:=x-n;
xn2:=x+n;
yn1:=y-n;
yn2:=y+n;
for i:=xn1 to xn2 do
for j:=yn1 to yn2 do
if (i>1) and (i<m) and (j>1) and (j<m) and (data[i,j]=1) then
begin
inc(ans);
end;
end;

begin
init;
change;
for i:=1 to m do
for j:=1 to m do
if data[i,j]=0 then
begin
count(1,1);
if ans>max then max:=ans;
end;
writeln(ans-1);
end.

3 条评论

  • @ 2014-11-03 11:00:05

    for x1:=1 to m-n+1 do
    for y1:=1 to m-n+1 do
    try(x1,y1);
    枚举每个攻击范围正方形的左上角
    procedure try(p,q:integer);
    var
    k:integer;
    begin
    if max=n*n then exit 如果发现已经有整个正方形被攻击那就没有必要继续找下去了(优化)
    else
    begin
    k:=0;
    for i:=p to p+n-1 do
    for j:=q to q+n-1 do
    if a[i,j]=1 then inc(k); 统计当前正方形的被攻击的数量
    end;
    if k>max then max:=k; 更新最大值
    end;

  • @ 2014-11-02 21:43:16

    program p1199;
    var
    a:array[1..10000,1..10000]of boolean;
    b,i,j,k,l,n,m,ans:longint;
    x:char;
    begin
    //assign(input,'fuck.txt');reset(input);
    // assign(output,'fuck2.txt');rewrite(output);
    fillchar(a,sizeof(a),false);
    readln(n);readln(m);
    for i:=1 to n do
    begin
    for j:=1 to n do
    begin
    read(x);if x='#' then a[i,j]:=true;
    end;
    readln;
    end;
    ans:=0;
    for i:=m to n do
    for j:=m to n do
    begin
    b:=0;
    for k:=i-m+1 to i do
    for l:=j-m+1 to j do
    if a[k,l] then inc(b);
    if b>ans then ans:=b;
    end;
    writeln(ans);
    end.
    AC

  • @ 2014-11-02 21:06:23

    program P1199;

    var
    n,m,k,j,i:longint;
    a:array[1..100,1..100]of char;

    procedure ds(q,w:longint);
    var i,j,l:longint;
    begin
    l:=0;
    for i:=q to q+m-1 do
    for j:=w to w+m-1 do
    if a[i,j]='#' then inc(l);
    if l>k then k:=l;
    end;

    begin
    readln(n,m);
    k:=0;
    for i:=1 to n do
    for j:=1 to n do read(a[i,j]);
    for i:=1 to n-m+1 do
    for j:=1 to n-m+1 do
    ds(i,j);
    write(k);
    end.

  • 1

信息

ID
1199
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
2725
已通过
1238
通过率
45%
被复制
7
上传者