問題
正方形のフィールドは M×M のセルで構成されています。各セルは 3 つの色のいずれか (1,2,3) で色付けされています。初期状態は色 1 のセルのいずれかに選ばれます。各ステップでは、フィールド内に留まりながら、1 セル上、下、左、または右に移動することが許可されています。
初期状態に関係なく、色 3 のセルに到達するために必要な最小ステップ数を定義してください。
フィールドには少なくとも 1 つの色 1 のセルと少なくとも 1 つの色 3 のセルが含まれていることに注意してください。
入力
入力は複数の入力ブロックで構成されています。各ブロックの最初の行にはフィールドのサイズ M が含まれています。その後、M 行にセルの色が続きます。
出力
各入力ブロックに対して、出力は初期状態に関係なく、色 3 のセルに到達するために必要な最小ステップ数を示す整数の 1 行で構成されるべきです。
サンプル入力
4
1223
2123
2213
3212
2
12
33
サンプル出力
3
1