Задача SOS!

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.
Руководители: к.ф-м.н, профессор Пирогов В.Ю,, к.п.н, доцент Слинкин Д.А,

Модераторы: xdsl, Vladislav_133

Задача SOS!

Сообщение xdsl 15 мар 2017, 11:18

Разбираем задачу, задаем вопросы, озвучиваем проблемы.
xdsl
 
Сообщения: 1226
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задача SOS!

Сообщение [DD] 14 апр 2017, 14:29

Используются stdin и stdout.
Подсветка синтаксиса: (main.rs) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка php
  1. use std::io::{self, Read};
  2. use std::collections::BTreeMap;
  3. //структура для хранения данных просто для удобства
  4. #[derive(Debug)]
  5. struct Ship {
  6.     pub ship : Vec<Vec<u8>>
  7. }
  8.  
  9. impl Ship {
  10.     //метод поиска пробоины или просто воды во внутренних помещениях(они после заполнения водой считаются пробоинами)
  11.      pub fn search(&self, line : usize, index : usize) -> Option<usize> {
  12.          let data = self.ship.get(line).unwrap();
  13.          for i in index..data.len() {
  14.              if data[i] == 48 {
  15.                  return Some(i);
  16.              }
  17.          }
  18.          None
  19.      }
  20.      // метод получения списка не затопленных отсеков на палубе
  21.      pub fn search_air(&self, line : usize) -> Vec<usize> {
  22.          let mut result = Vec::new();
  23.          let data = self.ship.get(line).unwrap();
  24.          for i in 0..data.len() {
  25.              if data[i] == 46 {
  26.                  result.push(i + 1);
  27.              }
  28.          }
  29.          result
  30.      }
  31.      // метод затапливает отсек и возвращает 1 если затопил и 0 в противоположном случае
  32.      pub fn replace(&mut self, line:usize, row:i16) -> u64 {
  33.          if line >= self.ship.len() || row < 0 || self.ship[line].len() <= row as usize{//проверка на то, что мы еще на корабле
  34.              return 0;
  35.          }
  36.          let mut data = self.ship.get_mut(line).unwrap();
  37.          let row = row as usize;
  38.          let has_dot = data[row] == 46;
  39.          if  has_dot{
  40.              data[row] = 48;
  41.              1
  42.          }else{
  43.              0
  44.          }
  45.      }
  46. }
  47.  
  48. fn main() {
  49.     let input = io::stdin();
  50.     let mut handle = input.lock();
  51.     let mut data = String::new();
  52.     handle.read_to_string(&mut data).unwrap();
  53.     let mut ship = Ship{ship : data.split("\n").map(|x|{x.bytes().collect()}).collect()};
  54.     let mut cnt:u64 = 0;
  55.     let mut air:BTreeMap<usize, Vec<usize>> = BTreeMap::new();//используется BTreeMap для того, что бы не сортировать по палубам
  56.     for i in 0..ship.ship.len() {//проходим по всем палубам
  57.         let mut index = ship.search(i, 0);//находим пробоину(ну или уже затопленный участок) на палубе
  58.         while index.is_some() {//если пробоина найдена
  59.             let mut row = index.unwrap() as i16;//запоминаем индекс в массиве
  60.             while ship.replace(i, row + 1) > 0 {//и топим все отсеки рассположенные справо и считаем их кол-во
  61.                 row += 1;
  62.                 cnt += 1;
  63.             }
  64.             let mut row = index.unwrap() as i16;//запоминаем индекс в массиве
  65.             while ship.replace(i, row - 1) > 0 {//и топим все отсеки слева
  66.                 row -= 1;
  67.                 cnt += 1;
  68.                 cnt += ship.replace(i + 1, row -1);//когда топим левые отсеки необходимо дополнительно пытаться топить отсеки снизу
  69.             }
  70.             cnt += ship.replace(i + 1, row);//топим отсек ниже найденного
  71.             index = ship.search(i, index.unwrap() + 1);// и ищем следующую пробоину на палубе
  72.         }
  73.         let line_air = ship.search_air(i);//находим все незатопленные отсеки и запоминаем их
  74.         if line_air.len() > 0 {
  75.             air.insert(i + 1, line_air);
  76.         }
  77.     }
  78.     //ну а тут уже просто вывод
  79.     println!("{}", cnt);
  80.     for (line, data) in air {
  81.         for idx in data {
  82.             println!("{} {}", line, idx);
  83.         }
  84.     }
  85. }
  86.  
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 158
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Задача SOS!

Сообщение xdsl 12 окт 2017, 11:37

Удивительно, это мозилловский Rust?
Первый раз вижу программу на нем и судя по всему, Вы используете его в практической работе. Для каких целей, если не секрет?
xdsl
 
Сообщения: 1226
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.


Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron