哦哦,忽视一下 $85 \sim 86$ 行。
by Eason_cyx @ 2023-08-16 11:08:51
我之前 $AC$ 过这题,可以参考一下我的代码(我不建议把 $8$ 个方向写 $8$ 次循环,建议将方向写为一个数组,搜索时直接调用)
```cpp
#include<bits/stdc++.h>
using namespace std;
int sx[9]={0,-1,-1,-1,0,0,1,1,1};
int sy[9]={0,0,1,-1,-1,1,1,0,-1};
int wx[5]={0,-1,0,0,1};
int wy[5]={0,0,1,-1,0};
struct Node
{
int x,y,val;
};
int main()
{
int n,m;
char p;
scanf("%d%d",&n,&m);
int a[n+5][m+5],book[n+5][m+5];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>p;
if(p=='O') a[i][j]=0;
else a[i][j]=1;
}
}
while(1)
{
int prx,pry,hax,hay,flag=1;
scanf("%d%d%d%d",&prx,&pry,&hax,&hay);
if(prx==0) break;
queue<Node> Q;
Q.push({hax,hay,0});
memset(book,0,sizeof(book));
book[hax][hay]=1;
while(Q.size())
{
int x0=Q.front().x,y0=Q.front().y,step=Q.front().val;
Q.pop();
for(int i=1;i<=8;i++)
{
int x1=x0,y1=y0;
while(x1>=1&&x1<=n&&y1>=1&&y1<=m&&a[x1+sx[i]][y1+sy[i]]==0)
{
x1+=sx[i],y1+=sy[i];
if(x1==prx&&y1==pry)
{
flag=0;
printf("%d\n",step);
break;
}
}
if(flag==0) break;
}
if(flag==0) break;
for(int i=1;i<=4;i++)
{
int fx=x0+wx[i],fy=y0+wy[i];
if(fx>=1&&fx<=n&&fy>=1&&fy<=m&&a[fx][fy]==0&&book[fx][fy]==0)
{
Q.push({fx,fy,step+1});
book[fx][fy]=1;
}
}
}
if(flag) printf("Poor Harry\n");
}
return 0;
}
```
by Jason0211 @ 2023-08-16 11:18:31
@[Jason0211](/user/724069) ee 好叭,~~虽然对我没啥用~~。
by Eason_cyx @ 2023-08-16 11:20:24
@[Eason_cyx](/user/741244) @[Eason_cyx](/user/741244) 用 vector
by xigou1834 @ 2023-10-02 09:49:59
@[Eason_cyx](/user/741244) :
```cpp
#include<bits/stdc++.h>
using namespace std;
vector<vector<char>>a;
vector<vector<bool>>vis;
vector<vector<bool>>vis1;
int q[16385][5], jx, jy, hx, hy, n, m, h, t;
const int dx[] = {0, 0, -1, 1, 1, 1, -1, -1};
const int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
void reset_a()
{
a.resize(n + 1, vector<char>(m + 1, ' '));
for(int i = 0;i <= n;i ++)
{
for(int j = 0;j <= m;j ++)
{
a[i][j] = ' ';
}
}
}
void reset_vis()
{
vis.resize(n + 1, vector<bool>(m + 1, false));
for(int i = 0;i <= n;i ++)
{
for(int j = 0;j <= m;j ++)
{
vis[i][j] = false;
}
}
}
void reset_vis1()
{
vis1.resize(n + 1, vector<bool>(m + 1, false));
for(int i = 0;i <= n;i ++)
{
for(int j = 0;j <= m;j ++)
{
vis1[i][j] = false;
}
}
}
void bfs()
{
if(vis[hx][hy])
{
cout << 0 << endl;
return ;
}
memset(q, 0, sizeof(q));
h = 1, t = 1;
q[1][1] = hx, q[1][2] = hy, q[1][3] = 0, q[1][4] = 0;
reset_vis1();
while(h <= t)
{
for(int i = 0;i < 4;i ++)
{
int nx = q[h][1] + dx[i], ny = q[h][2] + dy[i];
if(nx > 0 && nx <= n && ny > 0 && ny <= m && a[nx][ny] != 'X' && !vis1[nx][ny])
{
vis1[nx][ny] = true;
t ++, q[t][1] = nx, q[t][2] = ny, q[t][3] = h, q[t][4] = q[h][4] + 1;
if(vis[nx][ny])
{
cout << q[t][4] << endl;
return ;
}
}
}
h ++;
}
cout << "Poor Harry\n";
return ;
}
int main()
{
cin >> n >> m;reset_a();
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
cin >> a[i][j];
}
}
while(true)
{
cin >> jx >> jy >> hx >> hy;
if(jx == 0 && jy == 0 && hx == 0 && hy == 0) return 0;
reset_vis();
for(int i = 0;i < 8;i ++)
{
int nx = jx, ny = jy;
while(nx > 0 && nx <= n && ny > 0 && ny <= m && a[nx][ny] != 'X')
{
vis[nx][ny] = true, nx += dx[i], ny += dy[i];
}
}
bfs();
}
}
```
by xigou1834 @ 2023-10-02 10:18:17