Напишите алгоритм для Робота, который закрашивает все клетки, находящиеся непосредственно выше горизонтальной стены

Arsen

26

Алгоритм для решения данной задачи можно разделить на следующие шаги:

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

Давайте рассмотрим пример на основе следующего изображения:

\[
\begin{{matrix}}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{{matrix}}
\]

Где 0 - незакрашенная клетка, а 1 - закрашенная.

Шаги алгоритма:

1. Робот начинает движение в верхний левый угол комнаты: \((0, 0)\).
2. Клетка \((0, 0)\) не подлежит закрашиванию.
3. Робот двигается на одну клетку вправо и находится в клетке \((0, 1)\).
4. Клетка \((0, 1)\) подлежит закрашиванию. Робот закрашивает данную клетку.

Результат на данном шаге:

\[
\begin{{matrix}}
0 & \color{{red}}1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{{matrix}}
\]

5. Робот двигается на одну клетку вправо и находится в клетке \((0, 2)\).
6. Клетка \((0, 2)\) не подлежит закрашиванию.
7. Робот двигается на одну клетку вправо и находится в клетке \((0, 3)\).
8. Клетка \((0, 3)\) не подлежит закрашиванию.
9. Робот двигается на одну клетку вправо и находится в клетке \((0, 4)\).
10. Клетка \((0, 4)\) не подлежит закрашиванию.
11. Робот двигается на одну клетку вправо и находится в клетке \((0, 5)\).
12. Клетка \((0, 5)\) не подлежит закрашиванию.

Переходим на следующую строку.

13. Робот двигается на одну клетку вниз и находится в клетке \((1, 0)\).
14. Клетка \((1, 0)\) не подлежит закрашиванию.
15. Робот двигается на одну клетку вправо и находится в клетке \((1, 1)\).
16. Клетка \((1, 1)\) подлежит закрашиванию. Робот закрашивает данную клетку.

Результат на данном шаге:

\[
\begin{{matrix}}
0 & 1 & 0 & 0 & 0 & 0 \\
0 & \color{{red}}1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{{matrix}}
\]

17. Робот двигается на одну клетку вправо и находится в клетке \((1, 2)\).
18. Клетка \((1, 2)\) подлежит закрашиванию. Робот закрашивает данную клетку.

Результат на данном шаге:

\[
\begin{{matrix}}
0 & 1 & \color{{red}}1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{{matrix}}
\]

19. Робот двигается на одну клетку вправо и находится в клетке \((1, 3)\).
20. Клетка \((1, 3)\) не подлежит закрашиванию.
21. Робот двигается на одну клетку вправо и находится в клетке \((1, 4)\).
22. Клетка \((1, 4)\) не подлежит закрашиванию.
23. Робот двигается на одну клетку вправо и находится в клетке \((1, 5)\).
24. Клетка \((1, 5)\) не подлежит закрашиванию.

Переходим на следующую строку.

25. Робот двигается на одну клетку вниз и находится в клетке \((2, 0)\).
26. Клетка \((2, 0)\) не подлежит закрашиванию.
27. Робот двигается на одну клетку вправо и находится в клетке \((2, 1)\).
28. Клетка \((2, 1)\) не подлежит закрашиванию.
29. Робот двигается на одну клетку вправо и находится в клетке \((2, 2)\).
30. Клетка \((2, 2)\) подлежит закрашиванию. Робот закрашивает данную клетку.

Результат на данном шаге:

\[
\begin{{matrix}}
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & \color{{red}}1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{{matrix}}
\]

31. Робот двигается на одну клетку вправо и находится в клетке \((2, 3)\).
32. Клетка \((2, 3)\) не подлежит закрашиванию.
33. Робот двигается на одну клетку вправо и находится в клетке \((2, 4)\).
34. Клетка \((2, 4)\) подлежит закрашиванию. Робот закрашивает данную клетку.

Результат на данном шаге:

\[
\begin{{matrix}}
0 & 1 & 1 & \color{{red}}1 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{{matrix}}
\]

35. Робот двигается на одну клетку вправо и находится в клетке \((2, 5)\).
36. Клетка \((2, 5)\) не подлежит закрашиванию.

Переходим на следующую строку.

37. Робот двигается на одну клетку вниз и находится в клетке \((3, 0)\).
38. Клетка \((3, 0)\) не подлежит закрашиванию.
39. Робот двигается на одну клетку вправо и находится в клетке \((3, 1)\).
40. Клетка \((3, 1)\) не подлежит закрашиванию.
41. Робот двигается на одну клетку вправо и находится в клетке \((3, 2)\).
42. Клетка \((3, 2)\) не подлежит закрашиванию.
43. Робот двигается на одну клетку вправо и находится в клетке \((3, 3)\).
44. Клетка \((3, 3)\) не подлежит закрашиванию.
45. Робот двигается на одну клетку вправо и находится в клетке \((3, 4)\).
46. Клетка \((3, 4)\) не подлежит закрашиванию.
47. Робот двигается на одну клетку вправо и находится в клетке \((3, 5)\).
48. Клетка \((3, 5)\) не подлежит закрашиванию.

Переходим на следующую строку.

49. Робот двигается на одну клетку вниз и находится в клетке \((4, 0)\).
50. Клетка \((4, 0)\) не подлежит закрашиванию.
51. Робот двигается на одну клетку вправо и находится в клетке \((4, 1)\).
52. Клетка \((4, 1)\) не подлежит закрашиванию.
53. Робот двигается на одну клетку вправо и находится в клетке \((4, 2)\).
54. Клетка \((4, 2)\) не подлежит закрашиванию.
55. Робот двигается на одну клетку вправо и находится в клетке \((4, 3)\).
56. Клетка \((4, 3)\) не подлежит закрашиванию.
57. Робот двигается на одну клетку вправо и находится в клетке \((4, 4)\).
58. Клетка \((4, 4)\) не подлежит закрашиванию.
59. Робот двигается на одну клетку вправо и находится в клетке \((4, 5)\).
60. Клетка \((4, 5)\) не подлежит закрашиванию.

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

\[
\begin{{matrix}}
0 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{{matrix}}
\]

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