Задачка про острова

07.04.2009, 16:49. **Показов** 4385. **Ответов** 5

Студворк — интернет-сервис помощи студентам

На старых школьных олимпиадах была такая задачка:
Дана матрица (n*m), которая состоит из 1 и 0. Нули - это море, а единицы - острова. Если единицы стоят рядом по вертикали или горизонтали - то они образуют один остров. Острова могут быть как согнутые, так и продырявленные, т.е.

111
101
111

Единицы здесь образуют остров.

111
100
100

Тут тоже.

Нужно найти количество островов.

@yanyk1n · 07.04.2009, 17:05

Pascal
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
program kkkk;
const
maxn = 100;
var
N, M, K, answer : integer;
field: array [0..maxn+1, 0..maxn+1] of
integer;
procedure readdata;
var
i, x, y: integer;
begin
fillchar(field, sizeof(field), 0);
read(N, M, K);
for i:=1 to K do begin
read(x, y);
field[x, y]:=1;
end;
end;
procedure solve;
var
i, j: integer;
begin
answer:=0;
for i:=1 to N+1 do
for j:=1 to M+1 do begin
if field[i,j]<>field[i,j-1] then
inc(answer);
if field[i,j]<>field[i-1,j] then
inc(answer);
end;
 
begin
assign(input,'figure.in');reset(input);
assign(output,'figure.out');rewrite(output);
readdata;
solve;
writeln(answer);
close(input);
close(output);
end.

И эта задача была на областной по информатике (Моск. обл.) за 2006/2007 год...

@Varlock · 07.04.2009, 18:49

напомните плз, как работает inc(answer);?

а то ни разу его не юзал, и не уверен в том, что именно он делает)
просто из любопытства почитал код (скомпилить и проверить у меня счас возможности нет), и кусок кода:

Pascal
1
2
3
4
if field[i,j]<>field[i,j-1] then
inc(answer);
if field[i,j]<>field[i-1,j] then
inc(answer);

у меня вызывает сомнения, не должно ли там быть что-то типа:

Pascal
1
2
if (field[i,j]<>field[i,j-1]) and (field[i,j]<>field[i-1,j]) then
inc(answer);

и меня терзает смутное сомнение, что остров типа:

она посчитает как 3 острова а не как 1 +)
вобщем хотелось бы чтобы мои сомнения разбили или подтвердили ))

@Puporev · 07.04.2009, 19:03

inc - инкремент, то же что и i:=i+1;

@Varlock · 07.04.2009, 19:23

ну да) это совпадает с моей догадкой))
тогда предложенный код:

Pascal
1
2
3
4
if field[i,j]<>field[i,j-1] then
inc(answer);
if field[i,j]<>field[i-1,j] then
inc(answer);

будет добавлять один остров в случаях:

Code
1
01

Code
1
2
0
1

Code
1
10

и

Code
1
2
1
0

(надеюсь, ясно, что во всех 4-ёх случаях левый или верхний элемент не равен текущему)
т.е., например, остров:

будет посчитан как 4 острова в предложенном коде

т.е., ИМХО, здесь стоит менять условия)) (добавить проверку на равенство текущей клетки единице, и делать все проверки через "И" а не "ИЛИ", т.к. в данном варианте остров опять же
011
011
будет посчитан как 2 острова, а не как 1...)
и тогда ещё отдельная обработка первой строчки и первого столбца наверно появится...(кол-во единиц в них отдельно посчитать)
хотя опять же данный вариант совершенно не учитывает острова типа
00000
01010
01110
00000
(будет считать как два полюбому с данной логикой )) )

@yanyk1n · 07.04.2009, 22:04

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

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const // массив с направлениями соседних клеток
dx : array [1..4] of integer = (-1,1,0 ,0);
dy : array [1..4] of integer = (0 ,0,-1,1);
 
var count:integer;
 
procedure rec(x,y:integer);
var
 i,k,t:integer;
begin
 k:=0;
 if a[x,y] <> 0 then 
 begin //клетка не пуста
  a[x,y] := 0; //не просматриваем больше эту клетку
  for i:=1 to 4 do
  begin //рассматриваем 4 соседних
   rec(x+dx[i],y+dy[i]);
   if a[x+dx[i],y+dy[i]]=1 then inc(k);
   if k=0 then inc(count);
  end;
 end; 
end;

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	07.04.2009, 19:03
	inc - инкремент, то же что и i:=i+1; 0