結果

問題 No.124 門松列(3)
コンテスト
ユーザー tsukio
提出日時 2016-03-17 13:56:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,060 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 67,588 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 08:51:26
合計ジャッジ時間 1,799 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

struct Point {
	Point(int x, int y, int dir) {
		this->x = x;
		this->y = y;
		this->dir = dir;
	}
	int x;
	int y;
	int dir;
};

bool IsKadomatsuSequence(int prev, int current, int next) {
	if (prev < current && next < current && prev != next)
		return true;
	if (current < prev && current < next && prev != next)
		return true;
	return false;
}

int main() {
	const int INF = INT_MAX;
	const int MAX_WIDTH = 100;
	const int MAX_HEIGHT = 100;
	const int DIR_COUNT = 4;
	int dx[] = { -1, 1, 0, 0 };
	int dy[] = { 0, 0, -1, 1 };

	int w, h;
	cin >> w >> h;

	int board[MAX_WIDTH][MAX_HEIGHT];
	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			cin >> board[x][y];
		}
	}

	int dist[MAX_WIDTH][MAX_HEIGHT][DIR_COUNT];
	for (int x = 0; x < MAX_WIDTH; x++) {
		for (int y = 0; y < MAX_HEIGHT; y++) {
			for (int dir = 0; dir < DIR_COUNT; dir++) {
				dist[x][y][dir] = INF;
			}
		}
	}

	for (int dir = 0; dir < DIR_COUNT; dir++) {
		dist[0][0][dir] = 0;
	}
	dist[1][0][1] = 1;
	dist[0][1][3] = 1;
	
	queue<Point> points;
	points.push(Point(1, 0, 1));
	points.push(Point(0, 1, 3));

	while (!points.empty()) {
		Point current = points.front(); points.pop();
		int prev_x = current.x - dx[current.dir];
		int prev_y = current.y - dy[current.dir];
		int next_cost = dist[current.x][current.y][current.dir] + 1;

		for (int dir = 0; dir < DIR_COUNT; dir++) {
			int next_x = current.x + dx[dir];
			int next_y = current.y + dy[dir];

			if (next_x < 0 || next_y < 0 || next_x >= w || next_y >= h)
				continue;

			if (!IsKadomatsuSequence(board[prev_x][prev_y], board[current.x][current.y], board[next_x][next_y]))
				continue;
			
			if (next_cost >= dist[next_x][next_y][dir])
				continue;

			dist[next_x][next_y][dir] = next_cost;
			points.push(Point(next_x, next_y, dir));
		}
	}

	int ans = INF;
	for (int dir = 0; dir < DIR_COUNT; dir++) {
		ans = min(ans, dist[w - 1][h - 1][dir]);
	}

	cout << (ans == INF ? -1 : ans) << endl;

	return 0;
}
0