#include<iostream>
#include<queue>
using namespace std;

// 坐标的结构体
struct Pos{
	int x, y, step;
};
int n;
char mp[1005][1005];
bool vis[1005][1005];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,1,-1};
int sx,sy,ex,ey;

// bfs(x, y)表示从(x, y)走到终点的最短步数
int bfs(int x, int y){
	// 准备一个队列
	queue<Pos> q;
	// 起点入队
	q.push({x, y, 0});
	// 标记起点
	vis[x][y] = 1;
	// 遍历队列，从起点开始扩展
	while(!q.empty()){
		// 取出队首元素，开始扩展
		Pos t = q.front();
		// 队首元素出队
		q.pop();
		// 如果走到终点，返回为真
		if(t.x==ex && t.y==ey) return t.step;
		// 扩展这个点的相邻节点(上 下 左 右)
		for(int i=0;i<4;i++){
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			// 可行性验证
			if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mp[xx][yy]=='0'&&vis[xx][yy]==0){
				q.push({xx, yy, t.step+1});
				vis[xx][yy] = 1;
			}
		}
	}
	return 0;
}