50分,求帮调欸
查看原帖
50分,求帮调欸
1339308
cannotlauchdemo_exe楼主2024/8/24 13:30

......

#include<bits/stdc++.h>


const int N = 1e6+5;

int n, m, k;

char status[2005][2005];
long long tim[N];
int a[N];
int b[N];
bool vis[2005][2005];
int down_step, up_step;

int dir[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0}
};

struct node{
    int x, y, d_step, u_step;
    node(int input_x, int input_y, int input_d_step, int input_u_step) : x(input_x), y(input_y),d_step(input_d_step), u_step(input_u_step) {}
};

void bfs(){
    std::queue<node> q;
    q.push(node(1, 1, 0, 0));
    while(!q.empty()){
        node u = q.front();
        q.pop();
        if (u.x == n && u.y == m){
            down_step = u.d_step;
            up_step = u.u_step;
            return ;
        }
        for(int i = 0; i < 4;i++){
            int new_x = u.x + dir[i][0];
            int new_y = u.y + dir[i][1];
            int new_d_step = u.d_step;
            int new_u_step = u.u_step;
            if (new_x < 1 || new_x > n || new_y < 1 || new_y > m || status[new_x][new_y] == 'X' || vis[new_x][new_y] == 1) continue;
            if (i == 0 || i == 1){
                new_d_step++;
            }
            else {
                new_u_step++;
            }
            q.push(node(new_x, new_y, new_d_step, new_u_step));
            vis[new_x][new_y] = 1;
        }
    }
}

int main()
{
    std::cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            std::cin >> status[i][j];
        }
    }

    for(int i = 1; i <= k; i++){
        std::cin >> a[i] >> b[i];
    }

    
    bfs();

    for(int i = 1; i <= k; i++){
        tim[i] = down_step*a[i] + up_step*b[i];
    }

    long long min_time = *std::min_element(tim+1, tim+1+k);
    int count = std::count(tim+1, tim+1+k, min_time);

    std::cout << min_time << " " << count;
}
2024/8/24 13:30
加载中...