Submission #12898078


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int H, W; string A[50];
const int MA = 50 * 50 * 15;
int mi[50][50][15];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
int enc(int x, int y, int state) {
	return state * H * W + y * W + x;
}
// {x, y, state}
tuple<int, int, int> dec(int id) {
	return make_tuple(id % W, (id % (H * W)) / W, id / (H * W));
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> H >> W;
	rep(y, 0, H) cin >> A[y];

	queue<int> que;
	rep(y, 0, H) rep(x, 0, W) rep(state, 0, 10) mi[y][x][state] = -1;
	rep(y, 0, H) rep(x, 0, W) if (A[y][x] == 'S') {
		que.push(enc(x, y, 0));
		mi[y][x][0] = 0;
	}

	while (!que.empty()) {
		int q = que.front(); que.pop();
		int x, y, state;
		tie(x, y, state) = dec(q);

		rep(d, 0, 4) {
			int xx = x + dx[d];
			int yy = y + dy[d];
			if (0 <= xx && xx < W && 0 <= yy && yy < H) {
				if (mi[yy][xx][state] < 0) {
					mi[yy][xx][state] = mi[y][x][state] + 1;
					que.push(enc(xx, yy, state));
				}

				if (A[yy][xx] == char('1' + state)) {
					if (mi[yy][xx][state + 1] < 0) {
						mi[yy][xx][state + 1] = mi[y][x][state] + 1;
						que.push(enc(xx, yy, state + 1));
					}
				}
			}
		}
	}

	rep(y, 0, H) rep(x, 0, W) if (A[y][x] == 'G') {
		cout << mi[y][x][9] << endl;
	}
}





Submission Info

Submission Time
Task H - 1-9 Grid
User hamayanhamayan
Language C++ (GCC 9.2.1)
Score 6
Code Size 2721 Byte
Status
Exec Time 6 ms
Memory 3780 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 6 / 6 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 4 ms 3600 KB
02.txt 2 ms 3644 KB
03.txt 2 ms 3648 KB
04.txt 2 ms 3560 KB
05.txt 2 ms 3648 KB
06.txt 2 ms 3692 KB
07.txt 2 ms 3672 KB
08.txt 2 ms 3544 KB
09.txt 2 ms 3644 KB
10.txt 2 ms 3532 KB
11.txt 3 ms 3716 KB
12.txt 4 ms 3712 KB
13.txt 4 ms 3596 KB
14.txt 4 ms 3652 KB
15.txt 6 ms 3700 KB
16.txt 4 ms 3752 KB
17.txt 4 ms 3716 KB
18.txt 5 ms 3708 KB
19.txt 5 ms 3604 KB
20.txt 3 ms 3688 KB
21.txt 2 ms 3636 KB
22.txt 2 ms 3500 KB
23.txt 2 ms 3628 KB
24.txt 2 ms 3520 KB
25.txt 2 ms 3576 KB
26.txt 2 ms 3640 KB
27.txt 3 ms 3520 KB
28.txt 2 ms 3656 KB
29.txt 2 ms 3772 KB
30.txt 3 ms 3692 KB
31.txt 4 ms 3772 KB
32.txt 4 ms 3724 KB
33.txt 4 ms 3660 KB
34.txt 3 ms 3780 KB
35.txt 3 ms 3768 KB
36.txt 4 ms 3728 KB
s1.txt 2 ms 3588 KB
s2.txt 2 ms 3628 KB
s3.txt 2 ms 3524 KB