shaoningyuan @ 2024-05-22 16:02:39
大佬帮我看看为什么最后一个点WA了 此人原代码
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,ex,ey;
char mp[10005][10005];
bool vis[10005][10005];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
bool flag=0;
struct st{
int x,y,step;
}now,p,pp;
void bfs(int x,int y)
{
queue<st> que;
st now={x,y,-1};
vis[x][y]=1;
que.push(now);
while(!que.empty())
{
p=que.front();
que.pop();
for(int i=0;i<4;i++)
{
int xx=p.x+dx[i];
int yy=p.y+dy[i];
while(xx>=1&&xx<=n&&yy>=1&&yy<=n&&vis[xx][yy]==0&&mp[xx][yy]!='x')
{
pp.x=xx; pp.y=yy; pp.step=p.step+1;
que.push(pp);
vis[xx][yy]=1;
if(xx==ex&&yy==ey)
{
flag=1;
cout<<pp.step;
return ;
}
xx=xx+dx[i];
yy=yy+dy[i];
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='.')
{
vis[i][j]=0;
}
else if(mp[i][j]=='x')
{
vis[i][j]=1;
}
else if(mp[i][j]=='A')
{
sx=i;
sy=j;
vis[i][j]=0;
}
else if(mp[i][j]=='B')
{
ex=i;
ey=j;
vis[i][j]=0;
}
}
}
bfs(sx,sy);
if(flag==0)
{
cout<<"-1";
}
return 0;
}谢谢各位
by Delete_error @ 2024-06-06 22:48:38
//test
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,ex,ey;
char mp[10005][10005];
bool vis[10005][10005];
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
bool flag=0;
struct st{
int x,y,step;
}now,p,pp;
void bfs(int x,int y)
{
queue<st> que;
st now={x,y,-1};
vis[x][y]=1;
que.push(now);
while(!que.empty())
{
p=que.front();
que.pop();
for(int i=0;i<4;i++)
{
int xx=p.x+dx[i];
int yy=p.y+dy[i];
while(xx>=1&&xx<=n&&yy>=1&&yy<=n&&vis[xx][yy]==0&&mp[xx][yy]!='x')
{
pp.x=xx; pp.y=yy; pp.step=p.step+1;
que.push(pp);
vis[xx][yy]=1;
if(xx==ex&&yy==ey)
{
flag=1;
cout<<pp.step;
return ;
}
xx=xx+dx[i];
yy=yy+dy[i];
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='.')
{
vis[i][j]=0;
}
else if(mp[i][j]=='x')
{
vis[i][j]=1;
}
else if(mp[i][j]=='A')
{
sx=i;
sy=j;
vis[i][j]=0;
}
else if(mp[i][j]=='B')
{
ex=i;
ey=j;
vis[i][j]=0;
}
}
}
bfs(sx,sy);
if(flag==0)
{
cout<<"-1";
}
return 0;
}by Delete_error @ 2024-06-06 22:49:03
方向数组改一下玄学过了
by Delete_error @ 2024-06-06 22:53:03
这道题理论上不能过的，可能会被卡掉，正解应该是把来时的方向也打个添一维标记（个人想法若有错请指正&&不要脸的求关）
by Delete_error @ 2024-06-06 22:54:48
因为bfs不保证是最优策略，只保证最少步数，答案不一定是第一个达到的方案
by Delete_error @ 2024-06-06 22:56:06
或者用时间换，bfs不结束，更新每次最小答案
by Delete_error @ 2024-06-06 22:58:06
看看我的代码理解第一种做法&&双倍经验p2937，好像数据更强
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,h1,w1,h2,w2,vis[105][105][5];
ll dx[10]={0,0,0,1,-1};
ll dy[10]={0,1,-1,0,0};
char maze[1005][1005];
struct Node{
ll X,Y,sum;
};
queue<Node>q;
bool check(ll x,ll y,ll v){
if(x<=n&&x>=1&&y<=n&&y>=1&&(maze[x][y]=='.'||maze[x][y]=='B')&&vis[x][y][v]==0) return true;
return false;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>maze[i][j];
if(maze[i][j]=='A') h1=i,w1=j;
if(maze[i][j]=='B') h2=i,w2=j;
}
}
q.push((Node){h1,w1,-1});
while(!q.empty()){//bfs
Node u=q.front();
q.pop();
ll x=u.X,y=u.Y,s=u.sum;
s++;
for(int i=1;i<=4;i++){
if(vis[x][y][i]) continue;
vis[x][y][i]=1;
ll tx=x+dx[i],ty=y+dy[i];
while(check(tx,ty,i)){//一直走
if(tx==h2&&ty==w2){
cout<<s;
return 0;
}
q.push((Node){tx,ty,s});
vis[tx][ty][i]=1;
if(i==1) vis[tx][ty][2]=1;
else if(i==2) vis[tx][ty][1]=1;
else if(i==3) vis[tx][ty][4]=1;
else if(i==4) vis[tx][ty][3]=1;//相反的也走过
tx+=dx[i],ty+=dy[i];
}
}
}
cout<<-1;
return 0;
}