Submission #1295001
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 dx1[] = {0, -1, -1, 1, 0, -1}, dy1[] = {-1, -1, 0, 0, 1, 1};
int dx2[] = {0, 1, -1, 1, 0, 1}, dy2[] = {-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, ny;
if(y%2 == 0) {
nx = x + dx1[i], ny = y + dy1[i];
} else {
nx = x + dx2[i], ny = y + dy2[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
Submission Time |
|
Task |
B - Office Ninja |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1670 Byte |
Status |
AC |
Exec Time |
5 ms |
Memory |
256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
001-sample-01.txt, 002-sample-02.txt, 003-minimum-01.txt, 004-random-01.txt, 005-random-02.txt, 006-random-03.txt, 007-random-04.txt, 008-random-05.txt, 009-random-06.txt, 010-random-07.txt, 011-random-08.txt, 012-random-09.txt, 013-random-10.txt, 014-random-11.txt, 015-random-12.txt, 016-random-13.txt, 017-random-14.txt, 018-random-15.txt, 019-random-16.txt, 020-random-17.txt, 021-random-18.txt, 022-random-19.txt, 023-random-20.txt, 024-maximum-01.txt, 025-maximum-02.txt, 026-maximum-03.txt, 027-maximum-04.txt, 999-handmade-01.txt |
Case Name |
Status |
Exec Time |
Memory |
001-sample-01.txt |
AC |
1 ms |
256 KB |
002-sample-02.txt |
AC |
1 ms |
256 KB |
003-minimum-01.txt |
AC |
1 ms |
256 KB |
004-random-01.txt |
AC |
2 ms |
256 KB |
005-random-02.txt |
AC |
1 ms |
256 KB |
006-random-03.txt |
AC |
1 ms |
256 KB |
007-random-04.txt |
AC |
1 ms |
256 KB |
008-random-05.txt |
AC |
3 ms |
256 KB |
009-random-06.txt |
AC |
1 ms |
256 KB |
010-random-07.txt |
AC |
2 ms |
256 KB |
011-random-08.txt |
AC |
1 ms |
256 KB |
012-random-09.txt |
AC |
1 ms |
256 KB |
013-random-10.txt |
AC |
1 ms |
256 KB |
014-random-11.txt |
AC |
2 ms |
256 KB |
015-random-12.txt |
AC |
1 ms |
256 KB |
016-random-13.txt |
AC |
1 ms |
256 KB |
017-random-14.txt |
AC |
2 ms |
256 KB |
018-random-15.txt |
AC |
1 ms |
256 KB |
019-random-16.txt |
AC |
2 ms |
256 KB |
020-random-17.txt |
AC |
1 ms |
256 KB |
021-random-18.txt |
AC |
2 ms |
256 KB |
022-random-19.txt |
AC |
2 ms |
256 KB |
023-random-20.txt |
AC |
1 ms |
256 KB |
024-maximum-01.txt |
AC |
3 ms |
256 KB |
025-maximum-02.txt |
AC |
3 ms |
256 KB |
026-maximum-03.txt |
AC |
3 ms |
256 KB |
027-maximum-04.txt |
AC |
3 ms |
256 KB |
999-handmade-01.txt |
AC |
5 ms |
256 KB |