2020, група A, 10-12 клас
19
D.
ОГНИЩА
121
Условие
Годината е 2323, а човекът е Гошо! Въпреки че всичко в света вече е хай-тек, наш Гошо следва дълбока семейна традиция, датираща от незапомнени времена и се грижи за гората си.
За съжаление през 2323, човешката дейност почти е унищожила климата на Земята и гората на Гошо е едно от малкото оцелели места с богата растителност, но за съжаление, неговата гора е застрашена от горски пожари и е ваша задача да помогнете за опазването ѝ!
Благодарение на високите технологии вие имате възможност да наблюдавате гората в реално време чрез сателит. Този сателит има температурен сензор и може да ви даде информация в картата за всеки квадратен метър от гората дали в него има пожар или не. Вашата цел е да локализирате всички огнища и да подадете информация за техните координати, за да може противопожарните дронове да се погрижат за тези пожари.
Картата на гората ще получите под формата на таблица от нули и единици. Ако на дадено място стои 1, то вие ще знаете, че там има огън, а ако стои 0 - няма опасност. Огнището се формира от група единици, които са свързани заедно по хоризонтал, вертикал или диагонал. За да идентифицирате дадено огнище, трябва да подадете координатите на неговия горен ляв сегмент.
Вход:
На първия ред на стандартния вход е зададен броят T на тестовете. Всеки тест се състои от поредица от редове. На първия от тях се въвежда две цели числа - брой редове R и брой колони C на картата. На всеки следващите R реда се въвеждат поредица от по C цели числа на всеки от редовете, разделени с интервал. Всяко от тези числа ще е 0 или 1.
Изход:
За всеки тест, програмата ви трябва да изведе на отделен ред броя на мегабтайтите, които са останали накрая, за да може Гошо да ги сравни с тези, които ДалаверкаТЕЛ твърдят, че му
остава.
Ограничения:
R, C - цяло число в интервала [1; 100]
Примерен вход:
2
3 3
0 0 0
1 0 1
0 0 0
4 4
0 0 1 0
1 0 1 0
1 0 1 1
0 0 0 0
Примерен изход:
1 0
1 2
0 2
1 0