💉質問内容

問題に答える

💉にゅうしゅつりょく

🧺入力
第1行はN(1≦N≦1000),M(1≦M≦1000)を与える.次のN行はMの数字で地図を与えます.(1,1)と(N,M)は常に0であると仮定する.
🧺しゅつりょく
1行目に最短距離を出力します.不可能な場合は-1を出力します.

🔋サンプルI/O

🔮入力例1

6 4
0100
1110
1000
0000
0111
0000

🔮サンプル出力1

15

🔮入力例2

4 4
0111
1111
1111
1110

🔮サンプル出力2

-1

💉もんだいぶんせき

🔋ぶんかつ

BFS

🔋難易度

金貨IV

💉問題を解く

🔋解法

これは典型的なbfs問題である.
ただし,原価計算配列(visit)は3次元である.
なぜなら、現在の壁が破壊されることを確保するためです.
bfs関数の3番目のパラメータとしてlmxが1であり,これが最大破壊可能な壁数であることを示した.
問題は全部で壁を1つしか砕けないので、あなたに1つあげました.
bfs条件文ではadj[ny][nx]が1の場合はb>0を表し,破壊可能かどうかを確認する.bが0であれば、これ以上砕けないことを意味します.
逆にadj[ny][nx]が0の場合は異なる.訪問の有無を確認すれば大丈夫です

🔋ソースコード

#include <bits/stdc++.h>

constexpr int MAX = 1001;
constexpr int INF = 987654321;

const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };

int adj[MAX][MAX];
int visit[MAX][MAX][3];

int bfs(int N, int M, int lmx){
	std::queue<std::pair<std::pair<int, int>, int>>q;
	q.push({ { 0, 0 }, lmx });
	visit[0][0][lmx] = 1;
	
	while(!q.empty()){
		int y = q.front().first.first;
		int x = q.front().first.second;
		int b = q.front().second;
		q.pop();
		
		if(y == N - 1 && x == M - 1) return visit[y][x][b];
		
		for(int i=0;i<4;++i){
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(nx >= 0 && ny >= 0 && nx < M && ny < N){
				if(adj[ny][nx] == 1 && b > 0){
					visit[ny][nx][b - 1] = visit[y][x][b] + 1;
					q.push({ { ny, nx }, b - 1 });
				}
				else if(adj[ny][nx] == 0 && visit[ny][nx][b] == 0){
					visit[ny][nx][b] = visit[y][x][b] + 1;
					q.push({ { ny, nx }, b });
				}
			}
		}
	}
	
	return -1;
}

int main() {
	int N, M;
	std::cin >> N >> M;
	
	for(int i=0;i<N;++i){
		std::string room;
		std::cin >> room;
		
		for(int j=0;j<M;++j) adj[i][j] = room[j] - '0';
	}
	
	std::cout << bfs(N, M, 1);
}

これは私のアルゴリズム初心者にとってとても役に立つ問題だと思います.
実は私はbfs、最大流量、グラフの問題だけを解いたと思っていましたが、もうたくさん解けました.まだ遠いようですね.
このタイプの問題は初めて解くので、面白くて有益です.

💉終了時..。

気になる部分があればコメントで質問しましょう~