問題
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)なのでたどり着けない