use std::io::{self, Read};
use std::collections::BTreeMap;
//структура для хранения данных просто для удобства
#[derive(Debug)]
struct Ship {
pub ship : Vec<Vec<u8>>
}
impl Ship {
//метод поиска пробоины или просто воды во внутренних помещениях(они после заполнения водой считаются пробоинами)
pub fn search(&self, line : usize, index : usize) -> Option<usize> {
let data = self.ship.get(line).unwrap();
for i in index..data.len() {
if data[i] == 48 {
return Some(i);
}
}
None
}
// метод получения списка не затопленных отсеков на палубе
pub fn search_air(&self, line : usize) -> Vec<usize> {
let mut result = Vec::new();
let data = self.ship.get(line).unwrap();
for i in 0..data.len() {
if data[i] == 46 {
result.push(i + 1);
}
}
result
}
// метод затапливает отсек и возвращает 1 если затопил и 0 в противоположном случае
pub fn replace(&mut self, line:usize, row:i16) -> u64 {
if line >= self.ship.len() || row < 0 || self.ship[line].len() <= row as usize{//проверка на то, что мы еще на корабле
return 0;
}
let mut data = self.ship.get_mut(line).unwrap();
let row = row as usize;
let has_dot = data[row] == 46;
if has_dot{
data[row] = 48;
1
}else{
0
}
}
}
fn main() {
let input = io::stdin();
let mut handle = input.lock();
let mut data = String::new();
handle.read_to_string(&mut data).unwrap();
let mut ship = Ship{ship : data.split("\n").map(|x|{x.bytes().collect()}).collect()};
let mut cnt:u64 = 0;
let mut air:BTreeMap<usize, Vec<usize>> = BTreeMap::new();//используется BTreeMap для того, что бы не сортировать по палубам
for i in 0..ship.ship.len() {//проходим по всем палубам
let mut index = ship.search(i, 0);//находим пробоину(ну или уже затопленный участок) на палубе
while index.is_some() {//если пробоина найдена
let mut row = index.unwrap() as i16;//запоминаем индекс в массиве
while ship.replace(i, row + 1) > 0 {//и топим все отсеки рассположенные справо и считаем их кол-во
row += 1;
cnt += 1;
}
let mut row = index.unwrap() as i16;//запоминаем индекс в массиве
while ship.replace(i, row - 1) > 0 {//и топим все отсеки слева
row -= 1;
cnt += 1;
cnt += ship.replace(i + 1, row -1);//когда топим левые отсеки необходимо дополнительно пытаться топить отсеки снизу
}
cnt += ship.replace(i + 1, row);//топим отсек ниже найденного
index = ship.search(i, index.unwrap() + 1);// и ищем следующую пробоину на палубе
}
let line_air = ship.search_air(i);//находим все незатопленные отсеки и запоминаем их
if line_air.len() > 0 {
air.insert(i + 1, line_air);
}
}
//ну а тут уже просто вывод
println!("{}", cnt);
for (line, data) in air {
for idx in data {
println!("{} {}", line, idx);
}
}
}