Простой путь
(Время: 5 сек. Память: 512 Мб Сложность: 67%)
Дано поле размером N×M, клетки которого раскрашены в белый и чёрный цвет. По клеткам с белым цветом можно свободно перемещаться, а по чёрным клеткам перемещение невозможно.
Требуется определить: существует ли простой путь из клетки (r1,c1) в клетку (r2,c2). Известно, что стартовая клетка всегда находится не ниже и не правее, чем конечная. Под простым путем будем понимать непрерывный маршрут от одной клетки к другой, представляющий собой ломаную с не более чем двумя изгибами. Перемещаться можно только вправо или вниз.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M – размеры поля (1 ≤ N×M ≤ 106). В следующих N строках идет описание поля. Каждая строка состоит из нулей и единиц и имеет длину M. Единица в r-й строке на c-й позиции означает, что в клетке с координатами (r,c) находится белая клетка, а ноль обозначает чёрную клетку.
В следующей строке записано целое число Q – количество запросов (1 ≤ Q ≤ 105). Каждая из следующих Q строк содержит данные запроса в формате r1 c1 r2 c2 (1 ≤ r1 ≤ r2 ≤ N, 1 ≤ c1 ≤ c2 ≤ M). Данная строка описывает маршрут из клетки (r1,c1) в клетку (r2,c2).
Выходные данные
В выходной файл OUTPUT.TXT выведите непрерывную последовательность из Q цифр, где i-я цифра равна единице, если для i-го запроса во входных данных существует простой путь, либо нулю, если простого пути нет.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 7
1110010
1010010
1011110
0100100
0100110
0111000
8
1 1 3 6
1 2 4 5
4 2 4 2
1 6 5 6
2 4 3 4
2 3 2 6
3 3 5 5
3 3 5 6
| 10100011 |
Система оценки
Решения, работающие только для N×M ≤ 2500 и Q ≤ 50, будут оцениваться в 50 баллов.
Решения, работающие только для N×M ≤ 250 000 и Q ≤ 50 000, будут оцениваться в 80 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
