0121 - 滑った故の結末

時間制限 1 秒 / メモリ制限 32 MB / 得点 10 / Writer ei1435 / x 5 / 統計 /

    タグ:

TLE
1sec
MLE
32MB
得点
10

滑った故の結末

あるところにプログラマーパンツァーがいた。
彼は、数日前のプロコンでふがいない結果を残したことで、頭を冷やすため旅に出ることにしていた。
彼の旅にでた村は氷の街便座。(滑った)
ここの村の地面はすべて氷だ。一度その方向(4方向(上下左右))へ進むと自分の物理的な力で止まることは不可能。止まる方法は1つしかない
・氷塊に激突する
またこの村には大きな穴がある。
そこの穴にはいることで、入り口が消滅する代わりに、ペアである穴から抜けることができ、抜けた穴の上には止まった状況になる。(入口出口の指定はないため出口==入口という感覚でよい)

しかしここまで遙かな道のりを旅に出たパンツァーだが滑り続き抜けることができない可能性があるということを知って急に怖くなった。
そこであなたはそこの村の情報を入手し、彼がスタート地点から出発した際に抜け出すこと(ゴールにたどり着くこと)ができるかどうかを彼に伝えてほしい。
なお盤外にでた場合は抜け出すことは無可能とする。
与えられる情報は以下の通りだ。
・盤面の大きさ縦×横
・スタート地点、ゴール地点の座標。
・氷塊の数とその座標
・穴の個数(1個はペア)とその穴の入口出口それぞれの座標。

【注意点】 ・一度入ったループの入り口は同じ消滅してしまう(何もない状態になる) ・穴の上にきた場合は消滅していない限りペアの穴にとばなくてはならない ・氷塊にぶつかった際は氷塊の1つ前の場所で止まる ・ゴール地点は氷じゃないためゴール上を通過すれば抜け出させたと考えて良い。

入力

h w
sx sy gx gy
n
a0 b0
a1 b1
・
・
・
an-1 bn-1
m
lua0x lua0y lub0x lub0y
lua1x lua1y lub1x lub1y
・
・
・
luam-1x luam-1y lubm-1x lubm-1y

1行目:村の大きさ 縦*横
2行目:スタート地点のx座標、y座標 ゴール地点のx座標、y座標
3行目:氷塊の数n
4行目〜4+n-1行目:氷塊iのx座標,y座標
5行目:穴の数m
6行目〜6+m-1行目:ペアa穴のx座標、y座標 ペアb穴のx座標、y座標

出力

パンツァーが村から抜け出せる場合 "OK" を 抜け出せ内場合 "NO"を1行に出力せよ。

制約

全ての入出力ケースについて以下を満たす。

  • 1 ≦ h*w ≦ 30, n ≦ 10 , m ≦ 5

入出力例

入力例1

2 5
0 0 4 1
0
0

出力例1

NO

入力例2

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

出力例2

OK