Submission #1294942
Source Code Expand
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
typedef pair<PI, int> PPII;
string a[200];
int main(void){
int r, c;
cin >> r >> c;
PI s, t;
REP(i, 0, r) {
cin >> a[i];
REP(j, 0, c) {
if (a[i][j] == 's') {
s = PI(i, j);
} else if (a[i][j] == 't') {
t = PI(i, j);
}
}
}
queue<PPII> que;
que.push(PPII(s, 0));
int dx[6] = {1, 1, 0, -1, -1, 0};
int dy[6] = {0, 1, 1, 0, -1, -1};
vector<VI> dist(r, VI(c, 1e8));
while (not que.empty()) {
PPII t = que.front(); que.pop();
int dis = t.second;
int x = t.first.first;
int y = t.first.second;
if (dist[x][y] <= dis) { continue; }
dist[x][y] = dis;
REP(d, 0, 6) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
continue;
}
int weight = isdigit(a[nx][ny]) ? a[nx][ny] - '0' : 0;
que.push(PPII(PI(nx, ny), dis + weight));
}
}
cout << dist[t.first][t.second] << endl;
}
Submission Info
Submission Time |
|
Task |
B - Office Ninja |
User |
kobae964 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1531 Byte |
Status |
WA |
Exec Time |
108 ms |
Memory |
3200 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
WA |
15 ms |
640 KB |
005-random-02.txt |
WA |
5 ms |
384 KB |
006-random-03.txt |
WA |
9 ms |
512 KB |
007-random-04.txt |
WA |
1 ms |
256 KB |
008-random-05.txt |
WA |
54 ms |
1308 KB |
009-random-06.txt |
WA |
2 ms |
256 KB |
010-random-07.txt |
WA |
6 ms |
384 KB |
011-random-08.txt |
WA |
2 ms |
256 KB |
012-random-09.txt |
WA |
8 ms |
512 KB |
013-random-10.txt |
WA |
2 ms |
256 KB |
014-random-11.txt |
WA |
24 ms |
768 KB |
015-random-12.txt |
WA |
1 ms |
256 KB |
016-random-13.txt |
AC |
3 ms |
256 KB |
017-random-14.txt |
WA |
32 ms |
768 KB |
018-random-15.txt |
WA |
2 ms |
256 KB |
019-random-16.txt |
WA |
37 ms |
1408 KB |
020-random-17.txt |
WA |
1 ms |
256 KB |
021-random-18.txt |
WA |
22 ms |
768 KB |
022-random-19.txt |
WA |
48 ms |
1280 KB |
023-random-20.txt |
WA |
2 ms |
256 KB |
024-maximum-01.txt |
WA |
99 ms |
3072 KB |
025-maximum-02.txt |
WA |
103 ms |
3200 KB |
026-maximum-03.txt |
WA |
93 ms |
2816 KB |
027-maximum-04.txt |
WA |
108 ms |
3200 KB |
999-handmade-01.txt |
AC |
34 ms |
896 KB |