系数大了吧
上述代码逻辑是不管下一个点是否在边界内,先加进去,下一次再判。
而一般是先判再往队列加。
那么因此前者有一项的系数是后者的8倍(?),被卡常了
by K_Owen @ 2023-11-28 03:19:45
可是改了后还是90pts啊?
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int N = 4e2 + 10;
int n,m,x,y,ans[N][N];
bool vis[N][N];
struct Bit
{
int x,y,v;
};
queue <Bit> q;
bool check(int a,int b)
{ return !(a > n || a < 1 || b > m || b < 1);}
void bfs()
{
q.push({x,y,0});
int _x = x,_y = y;
while (!q.empty())
{
Bit tot = q.front();
q.pop();
int x = tot.x,y = tot.y,v = tot.v;
if (vis[x][y]) continue;
vis[x][y] = 1;
ans[x][y] = v;
if (check(x + 2,y + 1)) q.push({x + 2,y + 1,v + 1});
if (check(x + 1,y + 2)) q.push({x + 1,y + 2,v + 1});
if (check(x - 2,y + 1)) q.push({x - 2,y + 1,v + 1});
if (check(x - 1,y + 2)) q.push({x - 1,y + 2,v + 1});
if (check(x + 2,y - 1)) q.push({x + 2,y - 1,v + 1});
if (check(x + 1,y - 2)) q.push({x + 1,y - 2,v + 1});
if (check(x - 1,y - 2)) q.push({x - 1,y - 2,v + 1});
if (check(x - 2,y - 1)) q.push({x - 2,y - 1,v + 1});
}
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
if (ans[i][j] == 0 && i != _x && j != _y)
ans[i][j] = -1;
}
int main()
{
cin >> n >> m >> x >> y;
bfs();
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}
```
by Hope5365 @ 2023-12-10 19:52:31
@[Hope5365](/user/1004336) 你判 `-1` 的方法有点问题,你可以直接把 `ans` 数组初始化为 `-1`,如果走不到的话就不会改,只有能够到达的点才会被更改。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 4e2 + 10;
int n,m,x,y,ans[N][N];
bool vis[N][N];
const int dx[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
const int dy[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
struct Bit {
int x,y,v;
};
queue <Bit> q;
void bfs() {
q.push({x,y,0});
int _x = x,_y = y;
while (!q.empty()) {
Bit tot = q.front();
q.pop();
int x = tot.x,y = tot.y,v = tot.v;
if(vis[x][y])
continue;
ans[x][y] = v;
vis[x][y] = 1;
for(int i = 0; i < 8; ++i) {
int X = x + dx[i],
Y = y + dy[i];
if (vis[X][Y] || X > n || X < 1 || Y > m || Y < 1) continue;
q.push({X, Y, v + 1});
}
}
// for(int i = 1; i <= n; i ++)
// for(int j = 1; j <= m; j ++)
// if (ans[i][j] == 0 && i != _x && j != _y)
// ans[i][j] = -1;
}
int main() {
memset(ans, -1, sizeof ans);
cin >> n >> m >> x >> y;
bfs();
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}
by Walrus @ 2024-01-26 08:35:18
@[Hope5365](/user/1004336) 或者这样
```cpp
#include <iostream>
#include <queue>
#include <bits/stdc++.h>//memset 的库直接加也行,或者是手动初始化
using namespace std;
const int N = 4e2 + 10;
int n,m,x,y,ans[N][N];
bool vis[N][N];
struct Bit
{
int x,y,v;
};
queue <Bit> q;
bool check(int a,int b)
{ return !(a > n || a < 1 || b > m || b < 1);}
void bfs()
{
q.push({x,y,0});
int _x = x,_y = y;
while (!q.empty())
{
Bit tot = q.front();
q.pop();
int x = tot.x,y = tot.y,v = tot.v;
if (vis[x][y]) continue;
vis[x][y] = 1;
ans[x][y] = v;
if (check(x + 2,y + 1)) q.push({x + 2,y + 1,v + 1});
if (check(x + 1,y + 2)) q.push({x + 1,y + 2,v + 1});
if (check(x - 2,y + 1)) q.push({x - 2,y + 1,v + 1});
if (check(x - 1,y + 2)) q.push({x - 1,y + 2,v + 1});
if (check(x + 2,y - 1)) q.push({x + 2,y - 1,v + 1});
if (check(x + 1,y - 2)) q.push({x + 1,y - 2,v + 1});
if (check(x - 1,y - 2)) q.push({x - 1,y - 2,v + 1});
if (check(x - 2,y - 1)) q.push({x - 2,y - 1,v + 1});
}
}
int main()
{
memset(ans, -1, sizeof ans);
cin >> n >> m >> x >> y;
bfs();
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}
by Walrus @ 2024-01-26 08:37:34
@[woshifujiarui](/user/908424) 谢谢,一关!
by Hope5365 @ 2024-01-26 08:39:36
@[Hope5365](/user/1004336) 其实只需要改一个地方 你判断逻辑写错了。。然后就能过了
```cpp
if (ans[i][j] == 0 && (i != _x || j != _y))
```
by Aaa_liang @ 2024-01-26 08:52:14