徒弟的下山之路(广度优先搜索改进版)

Chains.Z edited 1 年,9 月前

根据 这辈子不可能刷oj的 大佬 的博客改进, 在此感谢大佬的代码
1. 去除了一些人类迷惑行为(指Node定义了time却不用)
2. 使用了更好的代码风格(指检查数组越界)

#include <bits/stdc++.h>
using namespace std;
typedef long long llt;
const llt N = 1011;
const int big_int = 1e9;
const int dx[4] = {0, 0, 1, 1};
const int dy[4] = {-1, 1, 0, 1};
llt way[N][N];
llt time_used[N][N];
struct Node
{
    int x, y;
    Node(int i, int j) : x(i), y(j){};
};

void clear(llt board[][N])
{
    for (llt i = 0; i < N; i++)
        for (llt j = 0; j < N; j++)
            board[i][j] = big_int;
}

int main()
{
    llt n;
    cin >> n;
    clear(way);
    clear(time_used);
    for (llt i = 0; i < n; i++)
        for (llt j = 0; j <= i; j++)
            cin >> way[i][j];
    queue<Node> order;
    order.push(Node(0, 0));
    time_used[0][0] = way[0][0];
    while (!order.empty())
    {
        Node a = order.front();
        order.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = a.x + dx[i];
            int yy = a.y + dy[i];
            int time = time_used[a.x][a.y] + way[xx][yy];
            if (yy >= 0 && yy <= xx && xx < n && (way[xx][yy] != big_int) && time < time_used[xx][yy])
            {
                time_used[xx][yy] = time;
                order.push(Node(xx, yy));
            }
        }
    }
    cout << time_used[n - 1][0];
}

Comments