Carlの迷路解法 - Problem

アリのCarlが帰ってきました！ピラミッドを旅した後、Carlはいくつかのアルゴリズムを研究することに決め、グリッド迷路を解くための新しいアルゴリズムを発明しました。その動作は以下の通りです。

Carlは迷路内のどこかから右を向いてスタートし、目的地に到達したいと考えています。
Carlがまだ目的地にいない間、以下の手順を繰り返します。
- もしCarlが左に90度回転して空きマスを向くことができるなら、左に90度回転し、その後1マス前進します。
- そうでなく、もし1マス前進できるなら、前進します。
- それ以外の場合、右に90度回転します。

Carlはこのアルゴリズムがうまくいくかどうかを知りたがっています。彼が確認するのを手伝ってください！

入力の最初の行には、迷路のサイズ（行数、列数）を示す2つの整数 $r$ と $c$ ($1 \le r, c \le 50$) が含まれます。迷路の左上の角のセルは $(1, 1)$ です。

次の行には、Carlの開始位置である行 $i_{start}$、列 $j_{start}$ ($1 \le i_{start} \le r, 1 \le j_{start} \le c$) を示す2つの整数が含まれます。

次の行には、Carlの目的地の位置である行 $i_{end}$、列 $j_{end}$ ($1 \le i_{end} \le r, 1 \le j_{end} \le c$) を示す2つの整数が含まれます。Carlの開始位置と目的地の位置は異なることが保証されています。

続く $r$ 行のそれぞれには、0 または 1 のみからなる $c$ 文字の文字列が含まれます。文字が 1 の場合、そのマスには障害物があり通行できません。それ以外の場合は空きマスです。Carlの開始位置と目的地の位置は空きマスであることが保証されています。

Carlが開始位置から目的地まで到達可能であれば 1 を、そうでなければ 0 を、単一の整数として出力してください。

QOJ.ac