0478 - tile広場

時間制限 1 秒 / メモリ制限 64 MB / 得点 5 / Writer ei1507 / x 23 / 統計 /


TLE
1sec
MLE
64MB
得点
5

問題

clover広場は一月前に改装され、完全なる平地になっている。
計画ではそこに範囲を決めて巨大な迷路を作る予定だが、実際に配置してみて
正しく迷路になっていなかったら大変である。
迷路の予定図のデータを送るので、そのデータから作成できる迷路が
正しく迷路になっているかどうかを調べて欲しい。

迷路は壁の費用がもったいないので、地面の色で道を区別することにしている。
それと担当者が考えるのを怠けたため、各場所に 2 * 2 の色の付いたタイルを置くことで作成する仕様となっている。
タイルの色は赤青黄の三色ある。
プレイヤーはスタート地点と同じ色のタイルの道しか進めない。
つまりタイルのない道も進めない。(重要)
迷路を配置する予定地の広さ、スタート地点とゴール地点の座標、配置するタイルの個数、タイルの左上の座標と色が入力されるので
スタート地点からゴール地点へたどり着けるかどうかを出力して欲しい。

入力

w h
sx sy gx gy
n
x1 y1 c1
x2 y2 c2
x3 y3 c3
:
xn yn cn

最初の行に予定地の広さ 2 ≤ w h ≤ 15 が与えられ、
次の行にスタート地点とゴール地点の座標 1 ≤ sx sy gx gy ≤ 15 が与えられ、
3行目には配置するタイルの個数 1 ≤ n ≤ 15 が与えられる。
4行目からn+4行目は左上の座標 1 ≤ x y ≤ 15 と、そのタイルの色 1 ≤ c ≤ 3が入力される。 タイルの色は 1,2,3 が各色に割り当てられている。 なおタイルの一部もしくは全体が重なった場合、後に入力されたタイルの色で上書きされるものとする。

出力

スタート地点からゴール地点へ行くことができれば "OK" を、 行くことができなければ "NO" を出力する。

入出力例

入力例1

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

出力例1

NO

入力例2

9 6
2 2 7 6
7
1 1 1
3 4 2
2 2 2
5 4 2
4 3 3
7 5 3
6 5 2

出力例2

OK

例1の解説

この入力だと

01100
01100
03322
02222
02233

という迷路が作られる。

s(2,3),g(5,5)なのでたどり着けない