题目描述

有一个仅由数字0和1组成n*n的迷宫，若你位于一格的1上，那么可以移动到相邻4格的某一格的1上。你的任务是，对于一个给定的迷宫，你需要判断从左上方(1,1)的位置上出发，是否能走到（n,n）的出口。如果能输出1，不能输出0。

输入格式

一个数 $n$，代表n*n的迷宫。 接着n行，每行n个数字，代表迷宫中对应格子的数字。

输出格式

能从（1，1）的位置走到（n,n）的位置上， 则输出1，否则输出0。

3
1 0 1
1 1 0
1 0 1

0

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10$。