Монокарп играет в компьютерную игру. Сейчас он хочет пройти первый уровень этой игры.
Уровень — это прямоугольное клеточное поле из $$$2$$$ строк и $$$n$$$ столбцов. Персонаж Монокарпа изначально стоит в клетке $$$(1, 1)$$$ — на пересечении $$$1$$$ строки и $$$1$$$ столбца.
Персонаж Монокарпа за одно действие может переместиться из одной клетки в другую, если они — соседние по стороне и/или углу. Формально, из клетки $$$(x_1, y_1)$$$ можно за одно действие переместиться в клетку $$$(x_2, y_2)$$$, если $$$|x_1 - x_2| \le 1$$$ и $$$|y_1 - y_2| \le 1$$$. Очевидно, выходить за границы уровня нельзя.
На некоторых клетках находятся ловушки. Если персонаж Монокарпа оказывается в такой клетке, он умирает, и игра заканчивается.
Чтобы пройти уровень, персонаж Монокарпа должен оказаться в клетке $$$(2, n)$$$ — на пересечении строки $$$2$$$ и столбца $$$n$$$.
Помогите Монокарпу определить, можно ли пройти уровень.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных, каждый из которых состоит из трех строк.
В первой строке задано одно целое число $$$n$$$ ($$$3 \le n \le 100$$$) — количество столбцов.
Далее следуют две строки, описывающие уровень. $$$i$$$-я из этих строк описывает $$$i$$$-ю строку уровня — строка состоит из символов 0 и 1. Символ 0 соответствует безопасной клетке, символ 1 — клетке с ловушкой.
Дополнительное ограничение на входные данные: клетки $$$(1, 1)$$$ и $$$(2, n)$$$ — безопасные.
Для каждого набора входных данных выведите YES, если уровень можно пройти, и NO, если нельзя.
4 3 000 000 4 0011 1100 4 0111 1110 6 010101 101010
YES YES NO YES
Рассмотрим пример из условия.
Возможный путь в первом наборе входных данных: $$$(1, 1) \rightarrow (2, 2) \rightarrow (2, 3)$$$.
Возможный путь во втором наборе входных данных: $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4)$$$.
Возможный путь в четвертом наборе входных данных: $$$(1, 1) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 4) \rightarrow (1, 5) \rightarrow (2, 6)$$$.
Название |
---|