LeetCode Weekly Contest 178 4問目 - Minimum Cost to Make at Least One Valid Path in a Grid [1368]

Source

LeetCode Weekly Contest 178
問題文

問題概要

省略

解法

省略

cLay（version 20200308-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

class Solution {
public:
  int minCost(vector<vector<int>>& A) {
    dummy_main();

    int X = A.size(), Y = A[0].size();
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int mask, sx, sy, sc, nx, ny, nc, d;
    DijkstraHeap<int> hp;
    dimcomp2 dm(X,Y);

    rep(i,X) rep(j,Y) A[i][j]--;

    hp.malloc(X*Y);
    hp.init(X*Y);

    hp.change(0,0);
    while(hp.size){
      mask = hp.pop();
      dm(mask, sx, sy);
      sc = hp.val[mask];
      if(sx==X-1 && sy==Y-1) return sc;

      rep(d,4){
        nx = sx + dx[d];
        ny = sy + dy[d];
        nc = sc + if[A[sx][sy]==d, 0, 1];
        if(nx < 0 || ny < 0 || nx >= X || ny >= Y) continue;
        hp.change(dm(nx,ny), nc);
      }
    }

    return -1;
  }
};

Current time: 2024年04月20日20時17分06秒
Last modified: 2020年03月08日10時11分55秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)