Прямоугольники - 2 уровень |
Условие: На квадратном клечатом листе бумаги размером 100х100 клеток нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются. Написать программу, которая считает число этих прямоугольников. Техническое условие: Ограничение по времени тестирования: по 1 секунде на один тест. Формат входных данных: Входной файл INPUT.TXT содержит массив 100х100, в котором элемент A[i,j]=1, если клетка [i,j] принадлежит какому-либо прямоугольнику, и A[i,j]=0, в противном случае. Формат выходных данных: В файл OUTPUT.TXT необходимо вывести единственное число - количество прямоугольников. Решение: ---------- cut ---------- Задача легко решается путем следующих рассуждений: прямоугольников столько, сколько их северо-западных (верхних левых) углов. Особенное внимание следует обратить на случай, когда угол стоит у границы поля. ---------- cut ---------- var i,j,S:integer; A:array[0..100,0..100] of byte; begin assign(input,'input.txt'); reset(input); for i:=0 to 100 do for j:=0 to 100 do if (i=0) or (j=0) then A[i,j]:=0 else read(A[i,j]); S:=0; for i:=1 to 100 do for j:=1 to 100 do if (A[i,j]=1) and (A[i-1,j]+A[i,j-1]=0) then s:=s+1; assign(output,'output.txt'); rewrite(output); write(S); end. |