SSOJ2315营救
4909+
作者：crxis 发布：2017-08-16 分类：广度优先搜索
题目大意：给出一个用0和1代表陆地还海洋的地图，问从某个位置到某个位置的最短路径是多少？
题目描述
铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。
通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明的是海洋。船只能从一个格子移到相邻的四个格子。
为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离？
输入
第一行为n,下面是一个n*n的0、1矩阵，表示海洋地图。（n<=1000）
最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。
输出
哥伦比亚号到铁塔号的最短距离，答案精确到整数。
样例输入
3
001
101
100
1 1 3 3
样例输出
4
解题思路
一个一个填格子，广度优先！因为深度优先，不能保证填进去的步数是最少步数，会导致重复搜索，效率极低，严重超时。
读入数据前，先让地图全是非0的数，这样就可以避免搜索过程中走到地图外面出现数组越界等错误。由于需要存储位置（坐标），可以开两个队列数组分别存储x和y，为了节省空间，我们可以把(x,y)转成一个k（如1005）进制数，即转成z=x*k+y，变回去的时候x=z/k，y=z%k。只有这个k比行号大就不会出现冲突了。
接下来就是裸的广搜：逐个出队，往4个方向试探，能走且没走过，就走下去，记录下一个位置的步数是当前位置步数加1，入队。直到队列为空或者到达目的地，搜索结束。输出时，由于起点是第1步（避免走回起点），题目不算起点那个位置，所有答案要减1。
程序实现
