3760: 逃出城堡
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:17
解决:11
题目描述
羊羊们选出的代表不负重望,击败了骄傲的 Jack。Jack 恼羞成怒,违反了 原则要抓小羊,情况紧急,羊羊们必须找到一条最短的路径逃出 Jack 的城堡。 Jack 的城堡是一个 n*m 的矩形,里面有一些地方可以通过(用 0 表示),有一些 地方则为墙或障碍物(用 1 表示),无法通过,小羊们处于(x,y)处,出口在 (n,m)处。可小羊们无法立刻求到这条路径,这时,善良而伟大的 Yyz 出现了, 他给了羊羊们城堡的地图和一台笔记本电脑。羊羊们要通过这来求出到出口的最短路径。
输入
第 1 行,两个正整数 n,m(n,m≤500),表示城堡的长和宽。 第 2~n+1 行,每行 n 个数字(0 和 1),表示此处城堡地形。 第 n+2 行,两个正整数 x,y(x,y 均不超过 n,m),表示小羊所处位置。
输出
一行,一个数,表示最短路径的长度
样例输入 复制
6 5
0 0 1 0 1
1 0 0 0 0
1 1 0 1 0
0 0 0 1 0
1 0 1 1 0
1 0 0 0 0
2 2
样例输出 复制
7