Submission #3767184
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},
{1, 0, -1, 0, 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
Submission Time |
|
Task |
B - Office Ninja |
User |
emthrm |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1700 Byte |
Status |
AC |
Exec Time |
5 ms |
Memory |
384 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 |
384 KB |
005-random-02.txt |
AC |
1 ms |
384 KB |
006-random-03.txt |
AC |
2 ms |
384 KB |
007-random-04.txt |
AC |
1 ms |
256 KB |
008-random-05.txt |
AC |
2 ms |
384 KB |
009-random-06.txt |
AC |
1 ms |
256 KB |
010-random-07.txt |
AC |
1 ms |
384 KB |
011-random-08.txt |
AC |
1 ms |
384 KB |
012-random-09.txt |
AC |
2 ms |
384 KB |
013-random-10.txt |
AC |
1 ms |
256 KB |
014-random-11.txt |
AC |
2 ms |
384 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 |
384 KB |
018-random-15.txt |
AC |
1 ms |
256 KB |
019-random-16.txt |
AC |
2 ms |
384 KB |
020-random-17.txt |
AC |
1 ms |
256 KB |
021-random-18.txt |
AC |
2 ms |
384 KB |
022-random-19.txt |
AC |
3 ms |
384 KB |
023-random-20.txt |
AC |
1 ms |
256 KB |
024-maximum-01.txt |
AC |
2 ms |
384 KB |
025-maximum-02.txt |
AC |
3 ms |
384 KB |
026-maximum-03.txt |
AC |
3 ms |
384 KB |
027-maximum-04.txt |
AC |
4 ms |
384 KB |
999-handmade-01.txt |
AC |
5 ms |
384 KB |