結果

問題 No.971 いたずらっ子
コンテスト
ユーザー kjnh10
提出日時 2020-01-17 23:35:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,575 bytes
コンパイル時間 2,212 ms
コンパイル使用メモリ 193,672 KB
実行使用メモリ 1,570,496 KB
最終ジャッジ日時 2024-06-26 01:24:37
合計ジャッジ時間 8,877 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:78:27: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   78 |   friend auto& operator<<(auto &os, Edge& e){
      |                           ^~~~
main.cpp:93:27: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   93 |   friend auto& operator<<(auto &os, Graph& G){
      |                           ^~~~

ソースコード

diff # 

// template version 1.15
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF=1e18;

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define divceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
  #define cerrendl 42
#endif
//}}}

using Pos = int;  // TODO: update if needed

// using Cost = pair<int,int>;  // TODO: update if needed
struct Cost{
  int x;
  int y;
  Cost() {x = -1; y=-1;}
  Cost(int _x, int _y) : x(_x), y(_y){}
  bool operator<(const Cost &r) const { return ((x + y) < (r.x + r.y));}
  bool operator==(const Cost&r) const {return x==r.x&&y==r.y;}
  friend ostream& operator<<(ostream&os,const Cost&c){
    return os << c.x << " " << c.y;
  }
};
Cost zerocost = Cost(0LL, 0LL);  // TODO: update if needed
Cost infcost = Cost(INF, INF);  // TODO: update if needed
// using Cost = pii;
// Cost zerocost = mp(0, 0);
// Cost infcost = mp(INF, INF);

struct Edge {
  Pos to;/*{{{*/
  Cost cost;
  Edge(Pos to, Cost cost): to(to), cost(cost) {
  }
  friend auto& operator<<(auto &os, Edge& e){
    os << e.to << " " << e.cost;
    return os;
  }/*}}}*/
};
struct Graph{
  unordered_map<Pos, vector<Edge>> all_edges;//Posがpiiでなくintならunordredの方が早い{{{
  void add_edge(Pos from, Pos to, Cost cost){
    all_edges[from].emplace_back(to, cost);
  }

  auto operator[](Pos pos) {
    return all_edges[pos];
  }

  friend auto& operator<<(auto &os, Graph& G){
    os << G.all_edges;
    return os;
  }/*}}}*/
};
struct Dist {
  unordered_map<Pos, Cost> data;/*{{{*/
  Cost operator[](Pos pos){
    if (data.find(pos)!=data.end()) return data[pos];
    else                      return infcost;
  }/*}}}*/
};

signed main() {
  // grid graphを通常のグラフに格納する。
  // (i, j) -> i*w + j
  // u -> (u/w, u%w)

  int h,w;cin>>h>>w;
  int n = h*w;
  int mindk = INF;
  vvi block(h, vi(w));
  rep(i, h){
    string s;cin>>s;
    rep(j, w){
      block[i][j] = (s[j]=='k'?1:0);
      if (block[i][j]) chmin(mindk, i+j);
    }
  }

  // vvi g(n);
  Graph G;

  int di[]={1, -1, 0, 0};
  int dj[]={0, 0, 1, -1};
  rep(i, h)rep(j, w){
    int u = i*w+j;

    rep(k, 4){
      int ni = i+di[k];
      int nj = j+dj[k];
      int v = ni*w + nj;
      if (is_in(ni, 0, h) && is_in(nj, 0, w)){
        G.add_edge(u, v, Cost(1LL, 0LL));
        // 自分から生える辺だけでよい。そうしないと二重辺になってしまう。
      }
    }
  }

  Dist d;  // 最短距離
  PQ<pair<Cost, Pos>> pq;
  pq.push(mp(zerocost, 0));
  while (!pq.empty()){
    auto cp = pq.top(); pq.pop();
    auto cost = cp.first;
    auto u = cp.second;
    if (cost < d[u]) {
      d.data[u] = cost;
      for (auto &edge: G[u]){
        int v = edge.to;
        // Cost ncost = Cost(cost.x, cost.y);
        Cost ncost = cost;
        dump(v, block[v/w][v%w]);
        if (!block[v/w][v%w]){
          ncost.x += 1;
          if (ncost < d[v]) pq.push(mp(ncost, v));
        }
        else{;
          ncost.x += 1;
          ncost.y += ncost.x;
          if (ncost < d[v]) pq.push(mp(ncost, v));
        }
      }
    }
  }
  rep(i, n){
    dump(d[i]);
  }
  cout << d[n-1].x+d[n-1].y << endl;

  return 0;
}
0