#P1746. 离开中山路

    ID: 777 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>广度优先搜索BFS搜索模拟队列

离开中山路

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后,打算坐车离开中山路。现在爱与愁大神在 x1,y1x_1,y_1 处,车站在 x2,y2x_2,y_2 处。现在给出一个 n×n(n1000)n \times n(n \le 1000) 的地图,00 表示马路,11 表示店铺(不能从店铺穿过),爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间,他要求最短到达目的地距离(每两个相邻坐标间距离为 11)。你能帮他解决吗?

输入格式

11 行包含一个数 nn

22 行到第 n+1n+1 行:整个地图描述(00 表示马路,11 表示店铺,注意两个数之间没有空格)。

n+2n+2 行:四个数 x1,y1,x2,y2x_1,y_1,x_2,y_2

输出格式

只有 11 行,即最短到达目的地距离。

3
001
101
100
1 1 3 3
4

提示

对于 20%20\% 数据,满足 1n1001\leq n \le 100

对于 100%100\% 数据,满足 1n10001\leq n \le 1000