有一道题不太明白,关于C++联系题,在刷题的时候改了好几次都没有改对,希望大家帮帮我,有没有一些代码的思路或者想法,伪代码也可以,内容中没有办法打出英文的大写哦,所以用了0代替,这个题目的数据范围比较大,是两千的一个数据范围,我在提交的时候提示答案错误17%
龙&虫
时间限制:1秒 内存限制:128M
题目描述
给出一张NxM的地图,在地图上有一只虫,样子却很像龙,而且嘴能快速的喷出一种毒液,瞬间杀死敌人
现在假设虫的初始位置在(X1,Y1),另外在(X2,Y2)处有一个敌人。假设虫移动一步需要单位1的时间,而杀死敌人不需要时间,并且虫的毒液射程无穷大,但毒液不能穿透阻碍物,虫只能攻击上下左右、左上、右上、左下、右下八个方向 请求出虫最少需要用多少时间才能消灭敌人
输入描述
第一行两个数N和M,表示矩阵的规模
接下来是NxM的矩阵,0代表空地,X代表障碍物
下面是若干行数据,每行为一对数据,分别是敌人的位置和虫的位置。显然,敌人和虫都不可能在障碍物上
以“0 0 0 0”为输入结束标志
输出描述
输出第一行为虫能消灭掉敌人的最短时间
显然,若能直接打到敌人,则时间为0,若无法消灭,则第二行再输出“Impossible”
样例
输入
3 3
000
XX0
0X0
2 3 3 1
0 0 0 0
输出
Impossible!
提示
对于30%的数据:NXM<=5000
对于50%的数据:NXM<=10000
对于100%的数据:NXM<=20000
#include<iostream>
#include <queue>
using namespace std;
struct node{
int x,y,step;
};
const int N = 2000;
int n,m;
int dx[8]={0,1,1,0,0,-1,-1,0};
int dy[8]={1,1,1,-1,-1,1,-1,-1};
char mp[N][N];
char v[N][N];
void bfs(int x1,int y1,int x2,int y2) {
for (int i = 0; i < 8; i++) {
for (int j = 1; 1; j++) {
int x = x1 + dx[i] * j;
int y = y1 + dy[i] * j;
if (mp[x][y] != 'O') {
break;
}
v[x][y] = '1';
}
}
v[x1][y1] = '1';
if (v[x1][y1] == 1) {
cout << 0 << endl;
return ;
}
queue<node> que;
que.push((node){x2, y2, 0});
v[x2][y2] = '2';
while (!que.empty()) {
node temp = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i];
int y = temp.y + dy[i];
if (v[x][y] == 1) {
cout << temp.step + 1 << endl;
return ;
}
if (mp[x][y]=='O'&&v[x][y]!='2') {
que.push((node){x,y,temp.step+1});
v[x][y]='2';
}
}
}
cout<<"Impossible!"<<endl;
}
int main(){
cin>>n>>m;
for (int i=1;i<=n;i++) {
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
int x1,x2,y1,y2;
while(cin>>x1>>y1>>x2>>y2&&x1){
bfs(x1,y1,x2,y2);
}
return 0;
}
这个是我写的代码,大家看看有什么问题吗?
帮忙debug一下