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
AC × 5
WA × 23
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