7-366 解救小鱼干

7-366 解救小鱼干

分数 10

全屏浏览

切换布局

作者 gongdan

单位 哈尔滨华德学院

有一天，腌制的小鱼干一个人去玩迷宫。但是方向感很不好的小鱼干很快就迷路了。珍惜头发的咸鱼得知后便立即去解救无助的好基友。咸鱼当然有备而来，已经弄清楚了迷宫的地图，现在咸鱼要以最快速度去救好基友了。你能帮帮他吗？

输入格式:

第一行有两个数n,m。n表示迷宫的行，m表示迷宫的列。接下来的n行m列为迷宫，0表示空地，1表示障碍物。最后一行4个数，前两个数为迷宫入口的x和y坐标。后两个为小哈的x和y坐标。

输出格式:

输出最短的步数

输入样例:

在这里给出一组输入。例如：

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3

输出样例:

在这里给出相应的输出。例如：

7

#include<stdio.h>
int n,m,min=9999999;
int x1,y1,x2,y2;
int arr[1000][1000];
void dfs(int x,int y,int *min,int step)
{
    if(x==x2-1&&y==y2-1)
    {
        *min=*min>step?step:*min;
    }
    if(x<0||x>n-1||y<0||y>m-1) return;
    if(arr[x][y]==1) return;
    arr[x][y]=1;
    dfs(x+1,y,min,step+1);
    dfs(x-1,y,min,step+1);
    dfs(x,y+1,min,step+1);
    dfs(x,y-1,min,step+1);
    arr[x][y]=0;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) scanf("%d",&arr[i][j]);
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    dfs(x1-1,y1-1,&min,0);
    printf("%d",min);
    return 0;
}