Submission #1294974

---

Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

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

char a[105][105];
int d[105][105];
signed main(void)
{
	int r, c, sx, sy, gx, gy;
	cin >> r >> c;
	REP(i, r) REP(j, c) {
		cin >> a[i][j];
		if(a[i][j] == 's') {
			sx = j; sy = i;
			a[i][j] = '0';
		}
		else if(a[i][j] == 't') {
			gx = j, gy = i;
			a[i][j] = '0';
		}
	}

	queue<PII> que;
	REP(i, r) REP(j, c) d[i][j] = INF;
	que.push({sx, sy});
	d[sy][sx] = 0;

	while(que.size()) {
		PII p = que.front(); que.pop();
		int x = p.first, y = p.second;
		if(x == gx && y == gy) continue;
		REP(i, 6) {
			int nx = x + dx[i], ny = y + dy[i];
			if(IN(0, c, nx) && IN(0, r, ny) && d[ny][nx] > d[y][x] + a[ny][nx] - '0') {
				que.push({nx, ny});
				d[ny][nx] = d[y][x] + a[ny][nx] - '0';
			}
		}
	}
/*
	REP(i, r) {
		REP(j, c) {
			cout << d[i][j] << " ";
		}
		cout << endl;
	}*/
	cout << d[gy][gx] << endl;
	return 0;
}

Submission Info

Judge Result