6 条题解
-
0Guest LV 0
-
0
#include<iostream>
using namespace std;
const int N=1001;
int n,x1,y1,x2,y2;
int a[N][N],xy[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool b[N][N];
struct node
{
int x,y,div;
}h[N*N];
bool check(int x,int y)
{
if(x>0&&x<n+1&&y>0&&y<n+1)
{
return true;
}
return false;
}
void sb(int x,int y)
{
int head=0,tail=1;
h[tail].x=x;
h[tail].y=y;
h[tail].div=0;
b[x][y]=1;
while(head<tail)
{
head++;
int xx,yy;
for(int i=0;i<4;i++)
{
xx=h[head].x+xy[i][0];
yy=h[head].y+xy[i][1];
if(b[xx][yy]==0&&check(xx,yy)&&a[xx][yy]==0)
{
b[xx][yy]=1;
tail++;
h[tail].x=xx;
h[tail].y=yy;
h[tail].div=h[head].div+1;
if(xx==x2&&yy==y2)
{
cout<<h[tail].div;
return ;
}
}
}
}
}
int main()
{
cin>>n;
char c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{cin>>c;
a[i][j]=c-'0';
}
}
cin>>x1>>y1>>x2>>y2;
sb(x1,y1);
return 0;
} -
-1
举一反三:
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
char a[1010][1010];
int n,sx,sy,ex,ey;
int head,tail,hx[maxn],hy[maxn],step[maxn]={0};
int nexx[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
void init()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>sx>>sy>>ex>>ey;
}
bool check(int x,int y)
{
if(x<0||x>n-1||y<0||y>n-1) return false;
return true;
}
void bfs(int txx,int tyy)
{
head=0,tail=1;
hx[tail]=txx,hy[tail]=tyy,step[tail]=0;
a[txx][tyy]='1';
while(head<tail)
{
head++;
for(int i=0;i<4;i++)
{
int tx,ty;
tx=hx[head]+nexx[i][0];
ty=hy[head]+nexx[i][1];
if(check(tx,ty)&&a[tx][ty]=='0')
{
tail++;
hx[tail]=tx;
hy[tail]=ty;
step[tail]=step[head]+1;
a[tx][ty]='1';
if((tx==ex-1)&&(ty==ey-1))
{
cout<<step[tail];
}
}
}
}
}
int main()
{
init();
bfs(sx-1,sy-1);
} -
-1
哈哈哈
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
int n,gx,gy,tx,ty;
char a[1010][1010];
int head,tail,step[maxn],hx[maxn],hy[maxn];
int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
void init()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>gx>>gy>>tx>>ty;
}
bool check(int x,int y)
{
if(a[x][y]=='1'||x<0||x>n||y<0||y>n) return 0;
return 1;
}
void bfs(int x,int y)
{
head=0;
tail=1;
hx[tail]=x;
hy[tail]=y;
step[tail]=0;
a[x][y]='1';
while (head<tail)
{
head++;
for(int i=0;i<4;i++)
{
int txx;
int tyy;
txx=hx[head]+f[i][0];
tyy=hy[head]+f[i][1];
if(check(txx,tyy))
{
tail++;
hx[tail]=txx;
hy[tail]=tyy;
step[tail]=step[head]+1;
a[txx][tyy]='1';
if(txx==tx-1&&tyy==ty-1) cout<<step[tail];
}
}
}
}
int main()
{
init();
bfs(gx-1,gy-1);
return 0;
} -
-1
正确答案:
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
int n,gx,gy,tx,ty;
char a[1010][1010];
int head,tail,step[maxn],hx[maxn],hy[maxn];
int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
void init()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>gx>>gy>>tx>>ty;
}
bool check(int x,int y)
{
if(a[x][y]=='1'||x<0||x>n||y<0||y>n) return 0;
return 1;
}
void bfs(int x,int y)
{
head=0;
tail=1;
hx[tail]=x;
hy[tail]=y;
step[tail]=0;
a[x][y]='1';
while (head<tail)
{
head++;
for(int i=0;i<4;i++)
{
int txx;
int tyy;
txx=hx[head]+f[i][0];
tyy=hy[head]+f[i][1];
if(check(txx,tyy))
{
tail++;
hx[tail]=txx;
hy[tail]=tyy;
step[tail]=step[head]+1;
a[txx][tyy]='1';
if(txx==tx-1&&tyy==ty-1) cout<<step[tail];
}
}
}
}
int main()
{
init();
bfs(gx-1,gy-1);
return 0;
} -
-1
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,gx,gy,tx,ty;
char a[maxn][maxn];
int head,tail,step[maxn],hx[maxn],hy[maxn];
int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
void init()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>gx>>gy>>tx>>ty;
}
bool check(int x,int y)
{
if(a[x][y]=='0'&&x>=0&&x<n&&y>=0&&y<n) return 1;
return 0;
}
void bfs(int x,int y)
{
head=0;
tail=1;
hx[tail]=x;
hy[tail]=y;
step[tail]=0;
a[x][y]='1';
while (head<tail)
{
head++;
for(int i=0;i<4;i++)
{
int txx;
int tyy;
txx=hx[head]+f[i][0];
tyy=hy[head]+f[i][1];
if(check(txx,tyy))
{
tail++;
hx[tail]=txx;
hy[tail]=tyy;
step[tail]=step[head]+1;
a[txx][tyy]='1';
if(txx==tx-1&&tyy==ty-1) cout<<step[tail];
}
}
}
}
int main()
{
init();
bfs(gx-1,gy-1);
return 0;
}
- 1
信息
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 229
- 已通过
- 46
- 通过率
- 20%
- 上传者