1024 Tester Program

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

テスタープログラム

問題

テスタープログラム。

このコンテストのために、私たちは次のような問題をデザインした(これ自身は解かなくてもよいことに注意！):

迷路のもう1つの壁

ACM/ICPCコンテストでは、「この迷路における最短経路を見つけろ」というような問題をよく見かける。それでは、これの逆を考えて次のようにしよう。「経路が与えられる。その経路が最短となるような迷路を見つけろ。」ここでは、経路は方眼の中央どうしを結ぶように水平または垂直に進むこととする。この問題は、方眼の点どうしを分割し、与えられた経路をスタートからゴールまでの唯一の最短経路とするような単位長の壁の集合を計算するものである。より問題を面白くするために、無駄な、つまりそれを取り除いても経路が唯一の最短経路であるような壁、があってはいけないことにする。次の例図では、8x5の方眼上を動く左上図のような経路を考える。上中央と右上図のような壁の配置は経路を一意に決定する。下段の2つは間違いである。
左下は最短経路が唯一ではなく、右下のものはいくつか余計な壁が存在する。

入力(オリジナルの問題の)

入力の最初の行はテストケースの数をあらわす整数t(1<=t<=10)を含む。続く行はテストケースである。各テストケースの最初の行は方眼の幅と高さを示す整数W,H(1<=W,H<=100)が空白を区切りとして書かれている。テストケースの2行目には経路が書いてある。経路は必ず左下隅(0,0)から始まる。経路はU(上),D(下),L(左),R(右)の4文字から構成される文字列(空白は含まない)からなる。経路は方眼の外に出ることはなく、自身と交差することもないとしてよい。経路は迷路のどこでも終わりうる。(つまり、隅または壁で終わる必要はない。)

出力(オリジナルの問題の)

i番目のテストケース(1から番号づけする)に対応する出力の最初の行は、解に使用された壁の数をあらわす整数Mを出力すること。続くM行には、それぞれの壁について、壁によって分離された2点をあらわす座標(x,y)からなる4つの整数を出力せよ。出力は一意でないことに注意せよ。出力に空行を含んではいけない。

入力例(オリジナルの問題の)

2
8 5
RRRUULLURRRRDDRRUUU
4 3
RRRUU

出力例(オリジナルの問題の)

19
0 0 0 1
1 0 1 1
2 0 2 1
2 1 3 1
3 0 4 0
3 1 4 1
3 2 4 2
3 2 3 3
2 2 2 3
4 2 4 3
0 3 0 4
1 3 1 4
2 3 2 4
3 3 3 4
4 3 4 4
5 3 5 4
5 3 6 3
5 2 6 2
6 1 6 2
2
2 2 3 2
2 2 2 1

以上がオリジナルの問題文である！遅くなったが、私たちはこの問題のためのテスタープログラムを書くのに時間を費やしたくないので、あなたにそれを書いてもらうことに決めたのである！

入力と出力をまとめて1つの入力テストケースとして、「CORRECT」または「INCORRECT」を、その出力が正しいかどうかを表わす文字列として出力するプログラムを書け。

入力

標準出力からオリジナルの問題における入力と出力を読みこむこと。オリジナルにおける出力はオリジナルにおける入力の直後にそのまま書いてある。
オリジナルにおける出力はフォーマットの間違いを含まないことに注意すること。例えば、
出力ファイルの行数は想定された通りであり、正しい。
出力行に余計なスペースは入っていない。
壁の記述は正しい、つまり4つの整数は迷路の矩形内にある正しい壁を正しく記述している。

出力

プログラムは各テストケースについて、オリジナルの問題における出力が正しいかどうかをあらわす1つの単語「CORRECT」または「INCORRECT」を出力せよ。

入力例

2
8 5
RRRUULLURRRRDDRRUUU
19
0 0 0 1
1 0 1 1
2 0 2 1
2 1 3 1
3 0 4 0
3 1 4 1
3 2 4 2
3 2 3 3
2 2 2 3
4 2 4 3
0 3 0 4
1 3 1 4
2 3 2 4
3 3 3 4
4 3 4 4
5 3 5 4
5 3 6 3
5 2 6 2
6 1 6 2
4 3
RRRUU
2
2 2 3 2
2 2 2 1

出力例

CORRECT
INCORRECT

出典

Tehran 2002, First Iran Nationwide Internet Programming Contest