admin管理员组

文章数量:1794759

【SSL

Oliver的救援

题目链接：Oliver的救援

题目描述

在你的帮助下，Oliver终于追到小X了，可有一天，坏人把小X抓走了。这正是Oliver英雄救美的时候。所以，Oliver又找到哆啦A梦，借了一个机器，机器显示出一幅方格地图，它告诉Oliver哪里能走，哪里不能走,。并且Oliver在这个地图的右下角，而小X在左上角。时间紧急，Oliver想知道，最少要走多少个格子,才能找到小X。（只能直走）。

输入格式

共N+1行，第一行为N，以下N行N列0-1矩阵，1表示不能通过,0表示可以通过(左上角和右下角为0). N<30.

输出格式

共一个数，为最少的走的格子数.

样例输入输出

输入

5
0 1 1 1 1
0 0 1 1 1
1 0 0 0 1
1 1 1 0 1
1 1 1 0 0

输出

9

解题思路

就是一道简单的BFS，几乎和电子老鼠闯迷宫一模一样。

参考程序

#include<iostream>
#include<cstdio>
using namespace std;
struct abc{int s,x,y,fa;
}f[1000010];
int n,x1,y1,x2,y2,a[1100][1010],hd=1,tl=1;
const int xj[5]={0,-1,1,0,0},yj[5]={0,0,0,-1,1};
bool check(int q,int p)
{if(q<1||q>n)return 0;if(p<1||p>n)return 0;if(a[q][p])return 0;return 1;
}
int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%1d",&a[i][j]);cin>>x1>>y1>>x2>>y2;f[1].x=x1;f[1].y=y1;while(1){for(int i=1;i<=4;i++)if(check(f[hd].x+xj[i],f[hd].y+yj[i])){tl++;a[f[hd].x+xj[i]][f[hd].y+yj[i]]=f[hd].s+1;f[tl].s=f[hd].s+1;f[tl].x=f[hd].x+xj[i];f[tl].y=f[hd].y+yj[i];f[tl].fa=hd;if(a[x2][y2]){cout<<a[x2][y2];return 0;} }hd++;}
}

本文标签： ssl