最短路

最短路

【题目描述】
石光中学正在进行地下水管线路改造,通往初中教学楼的道路被挖得坑坑洼洼,很不好走。历史学得不错的小A和小B决定学习哥伦布开辟一条校园新路线。通过多天的实地考察,他们终于画出了从校门口到初中教学楼的地形图!这张地图上划分成了n*n个比较小的单位,用1表示被挖开的路面, 用0表示平地。 同学只能在平地上走,且只能从一个格子移到相邻的4个格子里。为了不迟到,同学们都希望从校门口到教学楼最少要走多少距离。
【输入格式】
第一行,一个正整数n(n<=1000,表示地图的边长。
第2-n+1行,每行有n个0,或1,构成n*n的0,1矩阵,表示石光校园地形图
最后一行为4个小于n的整数 表示 校门口 和初中教学楼的坐标
【输出格式】
仅一个数,表示校门口到初中教学楼的最短距离 答案精确到整数

【输入输出样例】
count.in count.out
3
001
101
100
1 1 3 3 4