题目: 题目描述
在你的帮助下,Oliver终于追到小X了,可有一天,坏人把小X抓走了。这正是Oliver英雄救美的时候。所以Oliver又找到哆啦A梦,借了一个机器,机器显示出一幅方格地图,它告诉Oliver哪里能走,哪里不能走,并且知道Oliver和小X在这个地图的位置。时间紧急,Oliver想知道,最少要走多少个格子,才能找到小X。(只能直走)
输入
共N+2行。
第一行:N(N<=1000)
以下N行N列0-1矩阵,1表示不能通过,0表示可以通过(起点和终点为0),最后一行是他们两个的位置坐标,这些数用一个空格隔开。
输出 共一个数,为最少的走的格子数。
样例输入
5
01111
00111
10001
11101
11100
5 5 1 1
样例输出
8
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=20000;
const int dx[5] = { 0,0,0,1,-1 };
const int dy[5] = { 0,1,-1,0,0 };
int n, a, b, c, d, n1 = 0, read[N][N];
int st[20000000][4];
int h = 0, t = 1;
bool jc(int x, int y)
{
if (x > 0 && x <= n && y > 0 && y <= n && !read[x][y])
return 1;
else
return 0;
}
void bfs() {
st[1][1] = a;
st[1][2] = b;
st[1][3] = 0;
while (h <= t) {
h++;
for (int k = 1; k <= 4; k++)
{
if (jc(st[h][1] + dx[k], st[h][2] + dy[k])) {
t++;
st[t][1] = st[h][1] + dx[k];
st[t][2] = st[h][2] + dy[k];
st[t][3] = st[h][3] + 1;
read[st[t][1]][st[t][2]] = 1;
if (st[t][1] == c && st[t][2] == d)
{
cout << st[t][3];
h = 21123;
t = 0;
break;
}
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
string s;
scanf("%s" ,&s);
for (int j = 0; j < n; j++)
read[i][j + 1] = s[j] - 48;
}
scanf("%d%d%d%d", &a, &b, &c, &d);
bfs();
return 0;
}
问题:
时间超限