about summary refs log tree commit diff
path: root/12/TP-ThanhHoá-2009/bai5.pas
blob: 867b9d2cb932d1bfdab51be962254da8cfb90d52 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
uses
  sortnfind;

var
  f: text;
  rect: array of boolean;
  mem: array of intar;
  m, n: byte;
  tmp, i, idx0, idx1: smallint;


function locate(x: smallint): smallint;
  var
    i: smallint;

  begin
    for i := 0 to length(mem) - 1 do
      if binin(mem[i], x) then
        exit(i)
  end;


procedure mv(
  src: intar;
  var dest: intar
);

  var
    lendest, lensrc, i: smallint;

  begin
    lendest := length(dest);
    lensrc := length(src);
    setlength(dest, lendest + lensrc);

    for i := 0 to lensrc - 1 do
      dest[i + lendest] := src[i];

    setlength(src, 0);
    qsort(dest)
  end;


begin
  assign(f, 'BAI5.INP');
  reset(f);
  readln(f, m, n);
  setlength(rect, m * n);

  for i := 0 to m * n - 1 do
    begin
      read(f, tmp);

      if tmp = 0 then
        rect[i] := true
      else
        rect[i] := false
    end;
  close(f);

  setlength(mem, 0);

  for i := 0 to m * n - 1 do
    if rect[i] then
      begin
        idx0 := -1;
        idx1 := -1;

        if (i > 0) and rect[i - 1] then
          idx0 := locate(i - 1);

        if (i >= n) and rect[i - n] then
          if idx0 = -1 then
            idx0 := locate(i - n)
          else
            begin
              tmp := locate(i - n);

              if tmp < idx0 then
                begin
                  idx1 := idx0;
                  idx0 := tmp
                end
              else if tmp > idx0 then
                idx1 := tmp
            end;

        if idx0 + idx1 = -2 then
          begin
            setlength(mem, length(mem) + 1);
            setlength(mem[length(mem) - 1], 1);
            mem[length(mem) - 1][0] := i;
            continue
          end;

        setlength(mem[idx0], length(mem[idx0]) + 1);
        mem[idx0][length(mem[idx0]) - 1] := i;

        if idx1 > 0 then
          mv(mem[idx1], mem[idx0])
      end;

  tmp := 0;
  for i := 0 to length(mem) - 1 do
    if length(mem[i]) > tmp then
      tmp := length(mem[i]);

  assign(f, 'BAI5.OUT');
  rewrite(f);
  writeln(f, tmp);
  close(f)
end.