Поделитесь своими знаниями, ответьте на вопрос:
Пары. даны натуральное число n и n пар натуральных чисел. найти в каждой паре минимальное число и из всех таких чисел найти максимальное число. ввод в первой строке - натуральное число n ≤10. в каждой из последующих n строк - два натуральных числа, меньших 100, разделенных пробелом. вывод одно натуральное число.
1. Начнем с определения размеров нашего прямоугольника. По изображению видно, что он имеет размер 6 клеток по горизонтали и 4 клетки по вертикали.
2. Для начала создадим двумерный массив, который будет представлять наш прямоугольник. Заполним его значениями, где 0 означает пустую клетку, а 1 означает наличие стены. Наш массив будет выглядеть примерно так:
1 1 1 1 1 1
0 0 0 1 0 0
0 0 0 1 0 0
0 0 0 1 0 1
3. Далее, создадим функцию, которая будет осуществлять поиск в глубину и красить нижние клетки в каждом "кармане". Она будет принимать координаты текущей клетки, на которой находится робот, и двумерный массив прямоугольника. Давайте назовем эту функцию "раскрасить_карман".
4. Внутри функции проверим, находимся ли мы уже в нижней клетке кармана. Если да, то закончим выполнение функции. Если нет, то продолжим поиск.
5. Сначала проверим, сможем ли мы перейти на клетку слева. Для этого проверяем, что мы не находимся на самой левой границе прямоугольника и что клетка слева не является стеной. Если оба условия выполняются, то вызовем функцию "раскрасить_карман" для клетки слева.
6. Далее будем проверять, сможем ли мы перейти на клетку снизу. Для этого проверим, что мы не находимся на самой нижней границе прямоугольника и что клетка снизу не является стеной. Если оба условия выполняются, то вызовем функцию "раскрасить_карман" для клетки снизу.
7. Наконец, если клетка внизу не является стеной, вызовем функцию "раскрасить_карман" для клетки справа.
8. Исходя из приведенной картинки, начнем выполнение функции из клетки (0,0), то есть из самой левой верхней клетки. Затем алгоритм будет запускать сам себя для соседних клеток с помощью различных вызовов функции "раскрасить_карман".
9. В результате выполнения программы, наш прямоугольник будет представлен массивом следующего вида:
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
Т.е. все нижние клетки в каждом кармане окрасятся в цвет "1", что означает отметку роботом о покраске.
Вот так мы можем решить данную задачу с помощью алгоритма поиска в глубину.