白駿16137彦星織姫

質問リンク

リンク:https://www.acmicpc.net/problem/16137

質問する

キー(Key)

◆白俊研究所の問題のように、カササギ橋を置くことができる位置にカササギ橋を置き、シミュレーションを行う.
◆特に断崖が交差しているところにはカササギ橋が置けないのでチェック!(断崖絶壁座標では、時計回りに角角角をアルファベットで回転)
◆各座標には、前回カササギ橋を渡った場合と未カササギ橋を渡った場合の2つのケースがあるため、intdist[11][2]で宣言した後、その場所に保存するのに要する時間.
(カササギ橋を連続して渡ることができないので)
qとbeforeを連続的に通過して検査するかどうか.
distは2次元配列と宣言しただけで,再解して通過した.

試行錯誤

最初の解ではint dist[11][11]の代わりにboolvisit[11][11]配列が宣言された後,各座標にアクセスしたか否かのみが表示される.
そして,変数cntを設定することにより,qのサイクル周期に応じてcnt値を1増加させ,距離測定を試みる.
しかし、この方法ではカササギ橋の前で静かに待っている状況を計算するのは難しい.(x,y座標をqに残すことはできません...どうすればいいか悩んでいます...)
さんざん悩んだあげく、やっとdistを並べ替えた.

コード#コード#

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 2147483647
typedef struct info {
	int x, y;
	bool before;
}info;

int n, m;
int maps[11][11];
int dist[11][11];
int dx[4]{ 0,1,0,-1 };
int dy[4]{ 1,0,-1,0 };
bool can_struct(int x,int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

		int nx2 = x + dx[(i + 1) % 4];
		int ny2 = y + dy[(i + 1) % 4];
		if (nx2 < 0 || nx2 >= n || ny < 0 || ny >= n) continue;

		if (maps[nx][ny] == 0 && maps[nx2][ny2] == 0) return false;
	}
	return true;
}

int simulation() {
	queue<info> q;
	fill(&dist[0][0], &dist[10][11], INF);
	q.push({ 0,0,false });
	dist[0][0] = 0;
	int cnt = 0;
	while (!q.empty()) {
		int sz = q.size();
		for(int i=0;i<sz;i++){
			int x = q.front().x;
			int y = q.front().y;
			bool before = q.front().before;
			q.pop();

			

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (maps[nx][ny] == 0) continue;
				if (maps[nx][ny] == 1) {
					if (dist[nx][ny] > dist[x][y] + 1) {
						dist[nx][ny] = dist[x][y] + 1;
						q.push({ nx,ny,0 });
					}
				}
				else if (maps[nx][ny] > 1 && !before ) {
					int next = dist[x][y] + maps[nx][ny] - dist[x][y] % maps[nx][ny];
					if (dist[nx][ny]>next) {
						dist[nx][ny] = next;
						q.push({ nx,ny,true });
					}
				}
			}
		}
		cnt++;
	}
	return dist[n - 1][n - 1];
}

int select() {
	int minn = INF;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (maps[i][j] == 0 && can_struct(i, j)) {
				maps[i][j] = m;
				minn = min(minn, simulation());
				maps[i][j] = 0;
			}
		}
	}
	return minn;
}




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maps[i][j];
		}
	}
	cout<<select();
}

追加

BFS問題に何度も触れていたのである程度暗記していたので、何も考えずに方向をつかんで問題を解決するのは致命的でした.
あまり無理に考えてはいけない.問題自体はそんなに難しくないようですが、私は馬鹿です.これからは必ず復習しなければならない.