Описание
Генератор случайных карт известной игры Heroes of Might and Magic III создает острова, на которых изначально будут расположены герои. При такой генерации острова получаются различными по величине. Назовем коэффициентом несправедливости отношение площади наибольшего острова к площади наименьшего

Карта задается прямоугольником N×M, в каждой клетке которого записана цифра "0" - вода или цифра "1" - земля. Островом считается максимальное связное множество клеток, содержащих единички, т.е. такое множество клеток A, что:

  • из любой клетки A можно пройти до любой другой клетки A, переходя лишь через клетки A и их стороны

  • при добавлении к A любой другой клетки, содержащей 1, предыдущее условие нарушается

Задание
Определите коэффициент несправедливости


Входные данные
В первой строке входного файла содержатся числа N и M - размеры карты (1≤N,M≤1000). Далее записана сама карта - M строк по N чисел ("0" или "1") в каждой. Числа внутри строки разделяются пробелом

Выходные данные
В выходной файл вывести коэффициент несправедливости с 5 знаками после десятичной точки. Если на карте нет ни одного острова, вывести число "0"


Например:

ISLANDS.IN
7 6
1 1 0 0 0 0 0
0 1 0 1 0 0 0
1 1 0 1 1 0 0
1 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 0 1 0

ISLANDS.OUT
2.66667





Идеи
Операции над матрицей

Комментарии
На первый взгляд задача кажется совершенно стандартной, однако указанные в условии ограничения не позволяют решить ее привычным способом. Можно, конечно, попытаться разместить матрицу 1000×1000 в динамической памяти побитово и написать нерекурсивный вариант процедуры ее просмотра, чтобы не происходило переполнения стека. Этот способ приведет к успеху, однако мы рассмотрим более красивое решение данной задачи

Будем просматривать матрицу по строчкам сверху вниз. В каждый момент времени храним в памяти только текущую и предыдущую строчки матрицы. Также будем помнить максимальный и минимальный размеры островов, которые мы уже полностью просмотрели, текущие размеры островов, которые мы видим в данный момент, а для каждой единички в строках, которые мы просматриваем, - к какому острову она относится. Единичка (или группа единичек, стоящих подряд) в текущей строке может быть:

  1. Началом нового острова, если сверху (т.е. на той же позиции в предыдущей строке) от всех единичек стоят ноли. Например,

    1 0 0 0 0
    0 1 1 0 1

  2. Продолжением какого-то острова, начавшегося в предыдущей строке или раньше, если хотя бы над одной из единичек группы стоит единичка. Например,

    0 1 0 0
    0 1 1 0

  3. Одна группа единичек может служить продолжением сразу нескольких островов. Тогда эти острова объединяются (т.е. далее рассматриваются как один остров), а их текущие площади складываются. Например,

    0 1 0 1 0
    1 1 1 1 1

В этом случае при просмотре первой строки две единички будут рассматриваться как самостоятельные острова, а при рассмотрении второй строки «объединятся» в один остров. Однако, в следующем случае:

1 1 1 1
1 0 0 1
1 1 1 1

при рассмотрении третьей строки не нужно производить объединение островов, потому что эти единички принадлежат одному и тому же острову (т.к. при переходе от первой строки ко второй они являлись соседями единичек, принадлежащих одному острову)

 



 Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 65384,0,655360}
{$A+,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-}
{$N+}

program islands;
Const InputFile='islands.in';
      OutputFile='islands.out';
      MaxN=1000;
      MaxM=1000;
      MaxSp=15000;
      epsout=6;
      Dx: Array[1..4] Of Integer=( 0, 0,-1, 1);
      Dy: Array[1..4] Of Integer=(-1, 1, 0, 0);
Type Sset=Set Of 0..7;
     TSmall=Array[0..125] Of SSet;
 Var A: Array[1..MaxN] Of ^TSmall;
     N, M: Integer;
     Max, Min: LongInt;
     rs: Extended;
 
 Procedure AddA(i, j: Integer);
  Begin
   Include(A[i]^[j shr 3], j And 7);
  End;
 
 Procedure DeleteA(i, j: Integer);
  Begin
   Exclude(A[i]^[j shr 3], j And 7);
  End;
 
 Function ExisA(i, j: Integer): Boolean;
  Begin
   ExisA:=(j And 7) In A[i]^[j shr 3];
  End;
 
 Procedure Init;
  Var i, j, k: Integer;
   Begin
    Assign(Input, InputFile);
     Reset(Input);
      Read(M, N);
      For i:=1 To N Do Begin
       New(A[i]);
       FillChar(A[i]^, SizeOf(A[i]^), 0);
        For j:=1 To M Do Begin
         Read(k);
         If k=1 Then AddA(i, j);
       End;
      End;
     Close(Input);
    Max:=0; Min:=MaxLongInt;
   End;
 
Var Ox, Oy: Array[1..MaxSp] Of Integer;
 
 Procedure Delet(Const k, p: Integer; Var rs: LongInt);
  Var nx, ny, dwnf, i, upf, down, up: LongInt;
   Begin
    dwnf:=1; upf:=1; down:=1; up:=1;
    Ox[1]:=k; Oy[1]:=p; DeleteA(k, p);
    Repeat
     For i:=1 To 4 Do Begin
      nx:=Ox[dwnf]+Dx[i]; ny:=Oy[dwnf]+Dy[i];
      If (nx>0) And (ny>0) And (nx<=N) And (ny<=M) And ExisA(nx, ny) Then Begin
       DeleteA(nx, ny);
       Inc(up);
       upf:=upf Mod MaxSp + 1;
       Ox[upf]:=nx;
       Oy[upf]:=ny;
      End;
     End;
      Inc(down);
      dwnf:=dwnf Mod MaxSp + 1;
    Until down>up;
    rs:=up;
   End;
 
 Procedure Solve;
  Var i, j: Integer;
      rs: LongInt;
   Begin
    For i:=1 To N Do
    For j:=1 To M Do
     If ExisA(i, j) Then Begin
       Delet(i, j, rs);
       If rsThen Min:=rs;
       If rs>Max Then Max:=rs;
     End;
   End;
 
 Procedure Done;
   Begin
    Assign(Output, OutputFile);
     Rewrite(Output);
      If Max=0 Then WriteLn(0)
       Else Begin
         rs:=Max/Min;
         WriteLn(rs:0:epsout);
       End;
     Close(Output);
   End;
 
BEGIN
 Init;
  Solve;
 Done;
END.

 

© Особенности национальных задач по информатике