Вступ
Ми плануємо збудувати будиночок на дереві в лісі неподалік від нашого дому, щоб спостерігати за сходом і заходом сонця.
Ми отримали дані від місцевої геодезичної компанії про висоту кожного дерева в кожній прямокутній ділянці карти.
Нам потрібно проаналізувати кожну сітку на карті, щоб знайти гарні дерева для нашого будиночка на дереві.
Гарне дерево має бути одночасно:
- вищим за всі дерева на схід і на захід від нього, щоб мати якомога кращий вид на схід і захід сонця;
- нижчим за всі дерева на північ і на південь від нього, щоб якомога менше доводилося лазити по деревах.
Вказівки
Наше завдання - знайти потенційні дерева, на яких можна збудувати будиночок.
Компанія з даних надає дані у вигляді сіток, які показують висоти дерев.
Рядки сітки відповідають напрямку схід-захід, а стовпці - напрямку північ-південь.
Придатним буде дерево, найбільше у своєму рядку і водночас найменше у своєму стовпці.
У сітці може взагалі не бути хороших дерев.
Або може бути одне, або навіть кілька.
Ось сітка, у якій є рівно одне дерево-кандидат.
↓
1 2 3 4
|-----------
1 | 9 8 7 8
→ 2 |[5] 3 2 4
3 | 6 6 7 1
- У рядку 2 є значення 5, 3, 2 і 4. Найбільше значення - 5.
- У стовпці 1 є значення 9, 5 і 6. Найменше значення - 5.
Отже, точка [2, 1] (рядок: 2, стовпець: 1) - чудове місце для будиночка на дереві.
В Rust індекси починаються з 0
За домовленістю, вміст упорядкованих послідовностей значень у Rust нумерується («індексується»), починаючи з 0. Це так незалежно від того, що каже решта опису вправи в цьому README, зокрема посилання на індекси, які починаються з 1, тож, щоб перевести ці номери індексів у номери індексів Rust, доведеться відняти 1.
Зауваження щодо ефективності
У цій вправі для зберігання вмісту матриць використовується вектор векторів. Хоча цю вправу створено, щоб допомогти учням зрозуміти базові поняття про вектори, як-от індексування, і те, що вкладені типи даних допустимі, вектор векторів - неоптимальний вибір для високопродуктивної матричної алгебри та будь-якої подібної ефективної обробки більших обсягів даних.
Докладне пояснення цієї неефективності виходить за межі цієї вправи і цього навчального треку загалом. Цей аспект відомий як локальність кешу. Якщо ми хочемо дізнатися більше про деталі сучасної компʼютерної архітектури, гарний вступ до нього можна знайти, перейшовши за цим посиланням.
