cout_jerry @ 2022-08-20 22:10:20
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int mmap[1001][1001],n,zh[1000001][4],head=1,tail=1,x,y,xx,yy;
string a;
int bfs(int x,int y,int xx,int yy)
{
for(;;)
{
if(x==xx&&y==yy)
{
// cout<<"c:"<<zh[head][0]<<" "<<zh[head][1]<<" "
return zh[head][2];
}
if(mmap[x+1][y]==1)
{
zh[tail][0]=x+1;
zh[tail][1]=y;
zh[tail][2]=zh[head-1][2]+1;
tail++;
// cout<<"a:"<<x+1<<" "<<y<<" "<<zh[head-1][2]+1<<endl;
}
if(mmap[x][y+1]==1)
{
zh[tail][0]=x;
zh[tail][1]=y+1;
zh[tail][2]=zh[head-1][2]+1;
tail++;
// cout<<"a:"<<x<<" "<<y+1<<" "<<zh[head-1][2]+1<<endl;
}
if(mmap[x-1][y]==1)
{
zh[tail][0]=x-1;
zh[tail][1]=y;
zh[tail][2]=zh[head-1][2]+1;
tail++;
// cout<<"a:"<<x-1<<" "<<y<<" "<<zh[head-1][2]+1<<endl;
}
if(mmap[x][y-1]==1)
{
zh[tail][0]=x;
zh[tail][1]=y-1;
zh[tail][2]=zh[head-1][2]+1;
tail++;
// cout<<"a:"<<x<<" "<<y-1<<" "<<zh[head-1][2]+1<<endl;
}
x=zh[head][0];
y=zh[head][1];
head++;
// cout<<"b:"<<x<<" "<<y<<endl;
}
}
int main(){
std::ios::sync_with_stdio(false);//去同步优化
cin.tie(0);//缓存优化
cout.tie(0);//缓存优化
cin>>n;
for(register int i(1);i<=n;i++)
{
cin>>a;
for(int j(1);j<=n;j++)
{
mmap[i][j]=a[j-1]-47;
}
}
cin>>x>>y>>xx>>yy;
cout<<bfs(x,y,xx,yy);
return 0;
}
//for (register int i(1); i <= n; ++ i)循环加速
//register int 变量定义优化
//inline 函数优化
//cout<<111<<"\n";
本人已自闭,望大佬来调
by cout_jerry @ 2022-08-20 22:10:53
各路大神,救救蒟蒻吧
by NightTide @ 2022-08-20 22:28:06
@cout_jerry 边界
by NightTide @ 2022-08-20 22:28:56
看这个:
#include<bits/stdc++.h>
#define MAXN 1010
using namespace std;
const int rx[10] = {0, 1, -1, 0, 0};
const int ry[10] = {0, 0, 0, 1, -1};
struct node{
int x, y, dis;
};
int n, xs, xt, ys, yt;
int mapp[MAXN][MAXN];
bool vis[MAXN][MAXN];
void bfs(node st, node ed){
queue<node> q; q.push(st);
vis[st.x][st.y] = true;
while(!q.empty()){
node now = q.front(); q.pop();
for(int i = 1; i <= 4; i++){
node to = (node){now.x + rx[i], now.y + ry[i], now.dis + 1};
if(to.x < 1 || to.y < 1 || to.x > n || to.y > n) continue;//这里记得判断边界
if(vis[to.x][to.y] || mapp[to.x][to.y]) continue;
vis[to.x][to.y] = true;
q.push(to);
if(to.x == ed.x && to.y == ed.y){
printf("%d\n",to.dis);
return ;
}
}
}
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++){
char s[MAXN];
scanf("%s",s + 1);
for(int j = 1; j <= n; j++){
mapp[i][j] = s[j] - '0';
}
}
scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
bfs((node){xs, ys, 0}, (node){xt, yt, 0});
return 0;
}
by cout_jerry @ 2022-08-20 22:28:58
@Hoshino_kaede ???麻烦说详细点
by cout_jerry @ 2022-08-20 22:29:31
@Hoshino_kaede 边界不知道哪错了
by NightTide @ 2022-08-20 22:30:53
@cout_jerry 你代码不是枚举上下左右移动吗?移动的时候比如 x - 1
是有可能将 x
减成负数的,x + 1
也可能超过 y
同理
by bamboo12345 @ 2022-08-20 22:31:18
@cout_jerry 你这个bfs假了啊,如果这个点已经被搜过那么就不要再搜,你并没有体现这个事情
by NightTide @ 2022-08-20 22:31:53
对,这也是一方面,加一个
by NightTide @ 2022-08-20 22:32:05
@cout_jerry
by cout_jerry @ 2022-08-20 22:33:06
@bamboo123 感谢这位大佬的指点