用数组模拟队列
#include<iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N], d[N][N];
bool visited[N][N];
PII q[N*N];
int hh, tt = -1;
int n, m;
int bfs()
{
q[++tt] = { 0,0 };
d[0][0] = 0;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
while (hh <= tt)
{
PII k = q[hh];
hh++;
for (int i = 0; i < 4; i++)
{
int x = k.first + dx[i], y = k.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && !g[x][y] && !visited[x][y])
{
visited[x][y] = true;
q[++tt] = { x,y };
d[x][y] = d[k.first][k.second] + 1;
}
}
}
return d[n - 1][m - 1];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &g[i][j]);
cout << bfs() << endl;
return 0;
}
使用STL的queue
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N], d[N][N];
bool visited[N][N];
int n, m;
int bfs()
{
queue<PII> q;
q.push({ 0,0 });
d[0][0] = 0;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
while (!q.empty())
{
PII k = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = k.first + dx[i], y = k.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && !g[x][y] && !visited[x][y])
{
visited[x][y] = true;
q.push({ x,y });
d[x][y] = d[k.first][k.second] + 1;
}
}
}
return d[n - 1][m - 1];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &g[i][j]);
cout << bfs() << endl;
return 0;
}