結果

問題 No.124 門松列(3)
コンテスト
ユーザー masa
提出日時 2015-05-11 23:03:39
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 2,025 bytes
コンパイル時間 871 ms
コンパイル使用メモリ 88,816 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-05 23:16:37
合計ジャッジ時間 1,933 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <tuple>
#include <set>

using namespace std;

const int XY_SHIFT = 1000;

typedef tuple<int, int, int> TPL_III;

bool isKadomatsuSequence(int val) {
	int a = val / 100;
	int b = val / 10 % 10;
	int c = val % 10;

// printf("abc %d %d %d (%d)\n", a, b, c, val);

	if (b == 0) {
		return true;
	}

	if (a == 0) {
		return (b != c);
	}

	if (a == b || b == c || c == a) {
		return false;
	}
	if (b == max({a, b, c}) || b == min({a, b, c})) {
		return true;
	}
	return false;
}

int main() {
	int w, h;

	cin >> w >> h;
	vector< vector<int> > board(h, vector<int>(w, 0));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> board[i][j];
		}
	}
// cout << endl << endl;
	int dx[4] = {1, 0 , -1, 0};
	int dy[4] = {0, 1, 0, -1,};

	TPL_III tpl;

	vector< vector< set<int> > > came(h, vector<set<int> >(w, set<int>()));
	queue<TPL_III> que;

	int x, y, kdmt;
	int nx, ny, nkdmt, nstep;
	x = 0;
	y = 0;
	kdmt = board[y][x];
	que.push(make_tuple(y * XY_SHIFT + x, kdmt, 0));
	for (int i = 0; i < 1000; i++) {
		came[y][x].insert(i);
	}
	while(!que.empty()) {
		tpl = que.front();
		que.pop();

		x = get<0>(tpl) % XY_SHIFT;
		y = get<0>(tpl) / XY_SHIFT;

		kdmt = get<1>(tpl) * 10 % 1000;
		nstep = get<2>(tpl) + 1;

// printf("xy %d %d %d %d\n", x, y, get<1>(tpl), get<2>(tpl));

		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx < 0 || w <= nx || ny < 0 || h <= ny) {
				continue;
			}

			nkdmt = kdmt + board[ny][nx];
// printf("nxy %d %d %d\n", nx, ny, nkdmt);

			if (came[ny][nx].count(nkdmt) > 0) {
				continue;
			}

			if (isKadomatsuSequence(nkdmt)) {
				if (nx == w - 1 && ny == h - 1) {
					cout << nstep << endl;
					return 0;
				}

// printf("first came %d %d %d\n", ny, nx, nkdmt);
				came[ny][nx].insert(nkdmt);
				que.push(make_tuple(ny * XY_SHIFT + nx, nkdmt, nstep));
			}

		}
	}

	cout << -1 << endl;
	return 0;
}
0