結果

問題 No.971 いたずらっ子
コンテスト
ユーザー Haar
提出日時 2020-01-17 21:49:41
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,681 ms / 2,000 ms
コード長 7,724 bytes
コンパイル時間 9,038 ms
コンパイル使用メモリ 282,572 KB
最終ジャッジ日時 2025-01-08 18:27:04
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;


struct Point{
  int x, y;
  Point(): x(0), y(0){}
  Point(int x, int y): x(x), y(y){}
  Point& operator+=(const Point &a){this->x += a.x; this->y += a.y; return *this;}
  Point& operator-=(const Point &a){this->x -= a.x; this->y -= a.y; return *this;}
};

Point operator+(const Point &a, const Point &b){return Point(a.x+b.x, a.y+b.y);}
Point operator-(const Point &a, const Point &b){return Point(a.x-b.x, a.y-b.y);}
bool operator==(const Point &a, const Point &b){return a.x == b.x and a.y == b.y;}
bool operator!=(const Point &a, const Point &b){return !(a == b);}

std::ostream& operator<<(std::ostream &os, const Point &a){
  os << "(" << a.x << "," << a.y << ")";
  return os;
}

namespace grid{
  const std::vector<Point> dir4 = {Point(0,1), Point(0,-1), Point(1,0), Point(-1,0)};
  const std::vector<Point> dir8 = {Point(-1,-1), Point(-1,0), Point(-1,1), Point(1,-1), Point(1,0), Point(1,1), Point(0,-1), Point(0,1)};
}


template <typename Cost = int> class Edge{
public:
  int from,to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost): to(to), cost(cost){}
  Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}

  Edge rev() const {return Edge(to,from,cost);}
  
  friend std::ostream& operator<<(std::ostream &os, const Edge &e){
    os << "(FROM: " << e.from << "," << "TO: " << e.to << "," << "COST: " << e.cost << ")";
    return os;
  }
};

template <typename T> using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T> using Tree = std::vector<std::vector<Edge<T>>>;

template <typename C, typename T> void add_edge(C &g, int from, int to, T w){
  g[from].push_back(Edge<T>(from, to, w));  
}

template <typename C, typename T> void add_undirected(C &g, int a, int b, T w){
  g[a].push_back(Edge<T>(a, b, w));
  g[b].push_back(Edge<T>(b, a, w));
}


template <typename T, typename Checker, typename Generator>
Graph<T> grid_to_graph(int H, int W,
                       const std::vector<Point> &dir,
                       const Checker &check_passable,
                       const std::vector<std::vector<int>> &index,
                       const Generator &generate_edge_cost)
{
  Graph<T> ret(H * W);

  for(int i = 0; i < H; ++i){
    for(int j = 0; j < W; ++j){
      auto p = Point(i, j);

      for(auto &d : dir){
        auto q = Point(i, j) + d;

        if(q.x < 0 or q.x >= H or q.y < 0 or q.y >= W or not check_passable(p, q)) continue;

        auto e = Edge<T>(index[p.x][p.y], index[q.x][q.y], generate_edge_cost(p, q));
        
        ret[index[p.x][p.y]].emplace_back(e);
      }
    }
  }
  
  return ret;
}


template <typename T>
class Unbounded{
  enum class Tag { Value, PositiveInfinity, NegativeInfinity } tag;
  T val;
  
public:
  Unbounded(Tag tag): tag(tag){}
  Unbounded(const T &val): tag(Tag::Value), val(val){}

  auto& operator=(const T &rhs){
    this->tag = Tag::Value;
    this->val = rhs;
    return *this;
  }
  
  static auto pos_inf(){return Unbounded(Tag::PositiveInfinity);}
  static auto neg_inf(){return Unbounded(Tag::NegativeInfinity);}
  static auto value(const T &a){return Unbounded(a);}
  inline bool is_pos_inf() const {return tag == Tag::PositiveInfinity;}
  inline bool is_neg_inf() const {return tag == Tag::NegativeInfinity;}
  inline bool is_value() const {return tag == Tag::Value;}
  const T& get_value(){return this->val;}

  inline bool operator==(const Unbounded &rhs) const {
    if(this->tag == rhs.tag){
      if(this->tag == Tag::Value) return this->val == rhs.val;
      else return true;
    }
    return false;
  }

  friend std::ostream& operator<<(std::ostream &os, const Unbounded &rhs){
    switch(rhs.tag){
    case Tag::Value: os << rhs.val; break;
    case Tag::PositiveInfinity: os << "INF"; break;
    case Tag::NegativeInfinity: os << "-INF"; break;
    }
    return os;
  }
};


template <typename T, int MOD = 1000000007>
struct Dijkstra{
  using Result = Unbounded<T>;
  
  int n;
  std::vector<Result> dist;
  std::vector<int64_t> path_count;
  
  Dijkstra(const Graph<T> &graph, int src):
    n(graph.size()), dist(n, Result::pos_inf()), path_count(n)
  {
    std::vector<bool> check(n, false);
    std::priority_queue<std::pair<T,int>, std::vector<std::pair<T,int>>, std::greater<std::pair<T,int>>> pq;

    path_count[src] = 1;
    dist[src] = 0;

    pq.push({0, src});

    while(not pq.empty()){
      int i;
      T d;
      std::tie(d,i) = pq.top(); pq.pop();

      if(check[i]) continue;
      check[i] = true;

      for(auto &e : graph[i]){
        if(dist[e.to].is_pos_inf()){
          dist[e.to] = d + e.cost;
          path_count[e.to] = path_count[e.from];
          pq.push({dist[e.to].get_value(), e.to});
        }else{
          if(dist[e.to].get_value() > d + e.cost){
            dist[e.to] = d + e.cost;
            path_count[e.to] = path_count[e.from];
            if(not check[e.to]) pq.push({dist[e.to].get_value(), e.to});
          }else if(dist[e.to].get_value() == d + e.cost){
            (path_count[e.to] += path_count[e.from]) %= MOD;
          }
        }
      }
    }
  }
};





int main(){
  int H, W;
  while(cin >> H >> W){
    vector<string> a(H); cin >> a;

    
    auto index = vector(H, vector<int>(W));
    {
      int k = 0;
      REP(i,H){
        REP(j,W){
          index[i][j] = k++;
        }
      }
    }

    auto g = grid_to_graph<int>(H, W,
                                grid::dir4,
                                [](const Point &p, const Point &q){return q == p + Point(0, 1) or q == p + Point(1, 0);},
                                index,
                                [&](const Point &p, const Point &q){
                                  if(a[q.x][q.y] == 'k'){
                                    return 1 + q.x + q.y;
                                  }else{
                                    return 1;
                                  }
                                });

    auto res = Dijkstra(g, index[0][0]).dist;
    /*
    REP(i,H){
      REP(j,W){
        cerr << res[index[i][j]] << " ";
      }
      cerr << endl;
      }*/
    

    cout << res[index[H-1][W-1]] << endl;
    
    
  }
  
  return 0;
}
0