Решение задачи Игровой лабиринт Неко с Codeforces
Без пояснения   Просмотров: 105
NEKO#ΦωΦ только что купила новую игру на свой компьютер!
Главный пазл этой игры это прямоугольный лабиринт 2×n. Неко должна провести Некомими девочку из клетки (1,1) в клетку (2,n), тем самым выбравшись из лабиринта. Девочка может переходить только между клетками, соседними по стороне.
Однако, в некоторые моменты игры, некоторые клетки меняют своё состояние: или из земли в лаву (которая не позволяет проходить через клетку), или наоборот (что делает клетку проходимой вновь). Изначально ни в одной клетке лавы нет.
Спустя часы стриминга Неко выяснила, что есть всего q таких моментов, причём i-й из них переключает состояние клетки (ri,ci) (с земли на лаву, или наоборот). Неко хочет узнать для каждого момента из этих q, можно ли после него пройти из клетки (1,1) в (2,n) не проходя через клетки с лавой.
Неко великий игрок и стример, но она всё ещё не справляется с пазлами и задачками, требующими большой силы мозга. Не могли бы вы ей помочь?
Главный пазл этой игры это прямоугольный лабиринт 2×n. Неко должна провести Некомими девочку из клетки (1,1) в клетку (2,n), тем самым выбравшись из лабиринта. Девочка может переходить только между клетками, соседними по стороне.
Однако, в некоторые моменты игры, некоторые клетки меняют своё состояние: или из земли в лаву (которая не позволяет проходить через клетку), или наоборот (что делает клетку проходимой вновь). Изначально ни в одной клетке лавы нет.
Спустя часы стриминга Неко выяснила, что есть всего q таких моментов, причём i-й из них переключает состояние клетки (ri,ci) (с земли на лаву, или наоборот). Неко хочет узнать для каждого момента из этих q, можно ли после него пройти из клетки (1,1) в (2,n) не проходя через клетки с лавой.
Неко великий игрок и стример, но она всё ещё не справляется с пазлами и задачками, требующими большой силы мозга. Не могли бы вы ей помочь?