Задача в Си

Задача состоит в том, чтобы создать программу, которая будет оценивать распространение заболевания в офисе.
Офис имеет прямоугольную форму, люди сидят у столов, которые расположены в строки и столбцы. Место в офисе занято здоровым работником, больным работником или пустое. Больной работник в течении дня может заразить соседа слева, справа, спереди и сзади. На следующий день, новые больные заражают своих соседей. Болезнь не распространяется через пустые места.
На входе размер офиса (кол-во строк и столбцов). Потом вводится карта офиса, состоящая из 3 символов:
. (точка)-пустое место
о (маленькая о)-здоровый работник
! (воскл. знак)-больгой работник
Карта не содержит другие символы и пробелы, после каждой строки должен быть только знак новой строки "\n".
На выходе общее кол-во зараженных и продолжительность заражения (кол-во дней, в течение которых увеличивается число зараженных ).
Пример карты 1:
!...
....
оооо
Никто не заразится, т.е. продолжительность заражения 0.
Пример карты 2:
.о..ооо
о!о.ооо
.о..ооо
Продолжительность заражения 1.
Программа выводит ошибку если:
Размер офиса в не диапозоне от 1 до 500
После ввода размеров офиса нет \n
Карта не имеет форму прямоугольника
Карта имеет символ кроме "." "!" "о"
Пример работы программы:
Размер офиса:
4 4
oooo
oooo
oooo
!ooo
Зараженных: 16, время заражения: 6
Размер офиса:
4 4
o.oo
o.oo
o..o
!o.o
Зараженных: 5, время заражения: 3
Размер офиса:
4 4
oooo
o.oo
o..o
!o.o
Зараженных: 12, время заражения: 9
Размер офиса:
4 4
!oo!
o.oo
o..o
!o.o
Зараженных: 12, время заражения: 3
Размер офиса:
6 8
ooo!oooo
o......o
o.oooo.o
o.oooo.o
o......o
oooooooo
Зараженных: 24, время заражения: 12
Размер офиса:
7 8
!ooooooo
.......o
oooooooo
o.......
oooooooo
.......o
oooooooo
Зараженных: 35, время заражения: 34
Размер офиса:
2 2
.o
o.
Никто не заразился.
Размер офиса:
4 4
oooo
oooo
oooo
Xooo
Ошибка при входе.
Размер офиса:
4 4
oooo
ooooo
oooo
!ooo
Ошибка при входе.
Размер офиса:
5 4
oooo
oooo
oooo
!ooo
Ошибка при входе.
Если решать постоянно проверяя кто находится радом, то для больших чисел будут долгие вычисления. Нужен алгоритм для более быстрого решения!