AcWing 844. 走迷宫-python    原题链接    简单

作者： 作者的头像   Actor丶 ,  2020-02-12 19:36:23 ,  所有人可见 ,  阅读 1642

8


4 
"""
基本思想:
    bfs模板：
    1. 初始化队列
    2. while queue不为空
        3. 队顶元素出队
        4. 遍历，满足条件的入队

"""
def bfs():
    d[0][0] = 0
    # 1. 初始化队列
    queue = [(0,0)]    
    dx = [-1, 0 , 1, 0]    # !!!网格遍历的技巧：左，上，右，下
    dy = [0, 1, 0, -1]

    # 2. while queue不为空 
    while queue:
        # 3. 队顶元素出队
        x,y = queue.pop(0)
        # 4. 遍历，满足条件的入队
        for i in range(4):
            a = x+dx[i]
            b = y+dy[i]
            if a>=0 and a<n and b>=0 and b<m and g[a][b]==0 and d[a][b]==-1:
                queue.append((a,b))
                d[a][b] = d[x][y]+1
    print(d[n-1][m-1])

# 1. 输入示例
n, m = map(int, input().split())
g = [[-1 for i in range(m)] for j in range(n)]    # 存储输入的矩阵

for i in range(n):
    in_li = list(map(int, input().split()))
    for j in range(m):
        g[i][j] = in_li[j]
# 2. ！！！初始化状态
d = [[-1 for i in range(m)] for j in range(n)]    # 存储点到起点(0,0)的距离,-1表示未被访问过
bfs()

1 评论

用户头像
h闵   8个月前         踩      回复 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
// #include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int g[N][N];
int d[N][N];
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int n,m;

// vector<PII> q;
PII q[N * N];

int dfs()
{
    int hh = 0,tt = 0;
    q[hh] = {0,0};
    memset(d,-1,sizeof d);
    d[0][0] = 0;

    while(hh <= tt)
    {
        PII t = q[hh];
        hh++;

        for(int i = 0;i < 4;i++)
        {
            int x = t.first + dx[i],y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x,y};
            }
        }
    }

    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]);
        }
    }

    printf("%d\n",dfs());

    return 0;
}

为什么vector[HTML_REMOVED] q;就会报错
PII q[N * N];这样才可以啊，我不理解这个是为什么，原则上不都是可以的吗?