Submission #3767097

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

const int dy[] = {-1, -1, 0, 1, 1, 0};
const int dx[][6] = {
  {0, -1, -1, -1, 0, 1},
  {0, -1, 0, 1, 1, 1}
};

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int r, c; cin >> r >> c;
  vector<vector<char> > a(r, vector<char>(c));
  int sy, sx, ty, tx;
  REP(i, r) REP(j, c) {
    cin >> a[i][j];
    if (a[i][j] == 's') {
      sy = i; sx = j;
      a[i][j] = '0';
    } else if (a[i][j] == 't') {
      ty = i; tx = j;
      a[i][j] = '0';
    }
  }
  vector<vector<int> > dist(110, vector<int>(110, INF));
  dist[sy][sx] = 0;
  queue<pair<int, int>> qu;
  qu.push(make_pair(sy, sx));
  while (qu.size() > 0) {
    auto p = qu.front(); qu.pop();
    REP(i, 6) {
      int y = p.first + dy[i], x = p.second + dx[p.first%2][i];
      if (0 <= y && y < r && 0 <= x && x < c) {
        if (dist[y][x] > dist[p.first][p.second] + (a[y][x] - '0')) {
          dist[y][x] = dist[p.first][p.second] + (a[y][x] - '0');
          qu.push(make_pair(y, x));
        }
      }
    }
  }
  cout << dist[ty][tx] << '\n';
  return 0;
}

Submission Info

Judge Result