Эта проблема была задана Uber.

Вам дана двумерная матрица, в которой каждая ячейка состоит из /, \ или пустого места. Напишите алгоритм, который определяет, на сколько областей косая черта делит пространство.

Например, предположим, что входные данные для сетки три на шесть следующие:

\    /
 \  /
  \/

Считая края матрицы границами, это делит сетку на три треугольника, поэтому вы должны вернуть 3.

Я также создал видео с подробным решением проблемы.

Прежде чем перейти к проблеме, давайте визуализируем ее, нарисовав на бумаге и ручкой, как наша проблема будет выглядеть на самом деле.

Одно предположение, которое я делаю для этой задачи, заключается в том, что вместо пробелов я буду рассматривать . в качестве своего оператора, поэтому наша матрица будет выглядеть примерно так:

Косые линии делят нашу матрицу на три области, как показано ниже:

Теперь, когда у нас есть четкое представление о формулировке проблемы, давайте попробуем провести мозговой штурм, какой подход мы можем использовать.

Предположим, я нахожусь в клетке (i,j), теперь стою там и могу выбрать любое из 4 направлений (i-1,j) , (i,j+1) , (i+1,j) , (i,j-1) .

Давайте запишем наши выводы:

  1. Если я нахожусь в ячейке с символом \ или / (назовем такие ячейки блочными ячейками), то я точно не смогу пройти через нее.
  2. Если я нахожусь в ячейке, отличной от заблокированной, то я могу перемещаться в 4 направлениях, если только не столкнусь с заблокированной ячейкой или не выйду за пределы размеров матрицы.
  3. Мы можем использовать вспомогательную двумерную матрицу, чтобы отслеживать, какие ячейки мы уже посетили, чтобы не посещать их снова.

Давайте попробуем понять наши шаги обхода с точки зрения диаграмм:

  1. Мы будем использовать два цикла for для обхода матрицы, начнем с ячейки (0,0), и, поскольку она еще не посещается, мы начинаем обход, но это заблокированная ячейка, поэтому ничего не произойдет.
  2. Теперь переходим к ячейке (0,1), это пустая ячейка, поэтому отметим ее как посещенную.

3. Из (0,1) мы можем двигаться в 4 направлениях, но отсюда мы можем двигаться только в 1 направлении, то есть (0,2), и отметить его как посещенное.

4. Точно так же сейчас мы находимся в (0,2) , отсюда мы можем двигаться в 3 направлениях, но (0,1) но оно уже посещено, поэтому мы не будем пересекать его и посещать два других направления и продолжать этот процесс, пока мы не покроем всю возможную область , который будет выглядеть примерно так, как показано на изображении ниже.

5. Мы будем использовать глобальный счетчик для отслеживания количества регионов и будем увеличивать его каждый раз, когда завершим обход региона.

Наша окончательная диаграмма будет выглядеть примерно так:

Общая временная сложность программы составит O(n²). Поскольку мы пройдемся по всем ячейкам только один раз, а общее количество ячеек равно n X m

Пожалуйста, посмотрите на код, написанный на C++, чтобы понять реализацию кода.