_Mikasa @ 2023-03-16 15:28:20
#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0, 0,1,-1};
int dy[5]={0,1,-1,0, 0};
int n,m;
int sx,sy,e1,e2;
int mp[1000][1000];
int vis[1000][1000];
bool Noway(int nx,int ny)
{
if(nx<1||ny<1||nx>n||ny>n) return true;
if(vis[nx][ny]==1||mp[nx][ny]==-1) return true;
return false;
}
struct st
{
int s,x,y,fa;
bool operator < (const st &a) const
{
return s>a.s;
}
};
int bfs(int x,int y)
{
priority_queue <st> q;
st cur;
cur.s=0;cur.x=x;cur.y=y;cur.fa=100;
q.push(cur);
vis[x][y]=1;
while(!q.empty())
{
cur=q.top();
q.pop();
if(cur.x==e1&&cur.y==e2)
{
return cur.s;
}
for(int i=1;i<=4;i++)
{
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(Noway(nx,ny)) continue;
vis[nx][ny]=1;
st nxt;
nxt.x=nx;
nxt.y=ny;
nxt.s=cur.s;
if(cur.fa!=i) nxt.s++;
nxt.fa=i;
q.push(nxt);
}
}
return 0;
}
int main()
{
cin>>n;
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
char t;
cin>>t;
if(t=='A') sx=i,sy=j;
if(t=='B') e1=i,e2=j;
if(t=='x') mp[i][j]=-1;
}
}
cout<<bfs(sx,sy)-1;
return 0;
}
by mashduihca @ 2023-03-16 16:43:59
@_Mikasa 问你个问题,你有没有考虑过,如果对于一个位置,存在两种步数相同但朝向不同的走法,你的vis是无法区分的。
by _Mikasa @ 2023-03-16 16:50:33
@mashduihca 改好了 谢谢大佬%%%
我是:
by mashduihca @ 2023-03-16 16:52:27
@_Mikasa 别急。你是不是没图了。
by _Mikasa @ 2023-03-16 16:54:09
@mashduihca 想什么呢
by mashduihca @ 2023-03-16 16:55:42
@_Mikasa 我有832张顶针图。
by _Mikasa @ 2023-03-16 16:57:24
@mashduihca
by Caiest_Oier @ 2023-03-16 17:08:18
怎么又斗起图了
by _Mikasa @ 2023-03-16 17:17:08
@Caiest_Oier (
by Caiest_Oier @ 2023-03-16 17:19:58
@_Mikasa 你今天上午是不是JC了twc的号,然后私信叫我给你改
by _Mikasa @ 2023-03-16 17:23:00
@Caiest_Oier 不不不 这个是twc太害羞了不好意思发帖子他让我帮他问