Эта проблема была задана Uber.
Вам дана двумерная матрица, в которой каждая ячейка состоит из /
, \
или пустого места. Напишите алгоритм, который определяет, на сколько областей косая черта делит пространство.
Например, предположим, что входные данные для сетки три на шесть следующие:
\ /
\ /
\/
Считая края матрицы границами, это делит сетку на три треугольника, поэтому вы должны вернуть 3
.
Я также создал видео с подробным решением проблемы.
Прежде чем перейти к проблеме, давайте визуализируем ее, нарисовав на бумаге и ручкой, как наша проблема будет выглядеть на самом деле.
Одно предположение, которое я делаю для этой задачи, заключается в том, что вместо пробелов я буду рассматривать .
в качестве своего оператора, поэтому наша матрица будет выглядеть примерно так:
Косые линии делят нашу матрицу на три области, как показано ниже:
Теперь, когда у нас есть четкое представление о формулировке проблемы, давайте попробуем провести мозговой штурм, какой подход мы можем использовать.
Предположим, я нахожусь в клетке (i,j)
, теперь стою там и могу выбрать любое из 4 направлений (i-1,j)
, (i,j+1)
, (i+1,j)
, (i,j-1)
.
Давайте запишем наши выводы:
- Если я нахожусь в ячейке с символом \ или / (назовем такие ячейки блочными ячейками), то я точно не смогу пройти через нее.
- Если я нахожусь в ячейке, отличной от заблокированной, то я могу перемещаться в 4 направлениях, если только не столкнусь с заблокированной ячейкой или не выйду за пределы размеров матрицы.
- Мы можем использовать вспомогательную двумерную матрицу, чтобы отслеживать, какие ячейки мы уже посетили, чтобы не посещать их снова.
Давайте попробуем понять наши шаги обхода с точки зрения диаграмм:
- Мы будем использовать два цикла for для обхода матрицы, начнем с ячейки
(0,0)
, и, поскольку она еще не посещается, мы начинаем обход, но это заблокированная ячейка, поэтому ничего не произойдет. - Теперь переходим к ячейке
(0,1)
, это пустая ячейка, поэтому отметим ее как посещенную.
3. Из (0,1)
мы можем двигаться в 4 направлениях, но отсюда мы можем двигаться только в 1 направлении, то есть (0,2)
, и отметить его как посещенное.
4. Точно так же сейчас мы находимся в (0,2)
, отсюда мы можем двигаться в 3 направлениях, но (0,1)
но оно уже посещено, поэтому мы не будем пересекать его и посещать два других направления и продолжать этот процесс, пока мы не покроем всю возможную область , который будет выглядеть примерно так, как показано на изображении ниже.
5. Мы будем использовать глобальный счетчик для отслеживания количества регионов и будем увеличивать его каждый раз, когда завершим обход региона.
Наша окончательная диаграмма будет выглядеть примерно так:
Общая временная сложность программы составит O(n²). Поскольку мы пройдемся по всем ячейкам только один раз, а общее количество ячеек равно n X m
Пожалуйста, посмотрите на код, написанный на C++, чтобы понять реализацию кода.