E - マスゲーム 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

(12:44更新)オンサイト参加者の方へ 12:34までに提出された解答についてリジャッジを行いました．オープン参加者の方については引き続きリジャッジを行っていますので，お待ちください．
(14:47更新) オープン参加者の解答のリジャッジも完了しました．
12:34以降に提出された解答に対するテストケースは正しいものとなっています．

問題文

縦の長さが R、横の長さが C であるような 2 次元グリッド盤面があります。盤面の最も左上のマスの座標は (1,1) で、最も右下のマスの座標は (R,C) です。

この盤面に以下の操作を N 回繰り返します。

  • 盤面のある長方形区間に含まれる全てのセルを黒く塗る。具体的には、r,c,h,w が与えられるので、塗り始めの左上の座標を (r,c) として、そのマスを含めて縦幅 h マス、横幅 w マスであるような長方形区間に含まれる h×w 個のマスを全て黒く塗る。

黒いものが大好きなあなたは、今盤面上のある地点におり、別のある地点に黒いマスの上のみを辿ってたどり着きたいと思っています。あなたは、上下左右のいずれか近傍の 1 マスへの移動を自由に繰り返すことができます。盤面の外には出ることができません。

あなたのスタート地点のマスの座標 (r_s,c_s) とゴール地点のマスの座標 (r_g,c_g) といくつかの操作が与えられるので、スタート地点からゴール地点まで黒いマスの上だけを移動して、辿り着くことができるならば YES を出力し、辿りつけなかったりそもそもスタート地点やゴール地点がそもそも黒いマスでない場合は NO を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

R C
r_s c_s
r_g c_g
N
r_1 c_1 h_1 w_1
r_2 c_2 h_2 w_2
:
r_N c_N h_N w_N
  • 1 行目には、盤面の縦の長さと横の長さをそれぞれ表す整数 R,C (1 ≦ R,C ≦ 48) が与えられる。
  • 2 行目には、スタート地点のマスの座標を表す 2 つの整数 r_s (1≦ r_s ≦ R) と c_s (1≦ c_s ≦ C) が与えられる。
  • 3 行目には、ゴール地点のマスの座標を表す 2 つの整数 r_g (1≦ r_g ≦ R) と c_g (1≦ c_g ≦ C) が与えられる。
  • 4 行目には、操作回数を表す整数 N (1 ≦ N ≦ 1000) が与えられる。
  • 5 行目から N 行には、長方形の情報が与えられる。そのうち i 行目には、 i 番目の長方形の r,c,h,w を表す 4 つの整数 r_i (1≦ r_i ≦ R),c_i (1≦ c_i ≦ C),h_i (1≦ r_i+h_i-1 ≦ R),w_i (1≦ c_i+w_i-1 ≦ C) が与えられる。
  • スタート地点とゴール地点は必ず異なる。つまり、(r_s,c_s)≠(r_g,c_g) が成り立つ。

出力

1 行目に、問題文の要求にしたがって YES または NO を出力せよ。末尾の改行を忘れないこと。

入力例1

4 5
2 2
3 5
2
2 2 1 4
3 5 2 1

出力例1

YES

白いマスを .、黒いマスを # とすると、黒塗りの操作を施した後の盤面は、 以下の通りとなる。

.....
.####
....#
....#

さらに、スタート地点を S、ゴール地点を G とすると、以下のような位置関係となっている。

.....
.S...
....G
.....

入力例2

4 5
1 2
2 2
2
1 1 1 5
1 1 4 1

出力例2

NO

入力例3

4 5
1 1
1 3
3
1 1 1 1
1 2 1 1
1 3 1 1

出力例3

YES

入力例4

1 5
1 1
1 2
1
1 3 1 2

出力例4

NO

入力例5

1 5
1 3
1 2
1
1 3 1 2

出力例5

NO

入力例6

48 48
1 1
48 48
1
1 1 48 48

出力例6

YES