💉質問内容

問題に答える

💉にゅうしゅつりょく

🧺入力
第1行は2つの整数N,M(2≦N,M≦100)を与える.次のN行には迷路としてM個の整数がある.各数を入力として加算します.
🧺しゅつりょく
出力は最初の行の最小セル数を通過する必要があります.常に到着位置まで移動できる場合のみ、入力として使用されます.

🔋サンプルI/O

🔮入力例1

4 6
101111
101010
101011
111011

🔮サンプル出力1

15

🔮入力例2

4 6
110110
110110
111111
111101

🔮サンプル出力2

9

🔮入力例3

2 25
1011101110111011101110111
1110111011101110111011101

🔮サンプル出力3

38

🔮入力例3

2 25
1011101110111011101110111
1110111011101110111011101

🔮サンプル出力3

38

🔮入力例4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

🔮サンプル出力4

13

💉もんだいぶんせき

🔋ぶんかつ

BFS
ダエストラ

🔋難易度

シルバーI

💉問題を解く

🔋解法

問題は、ダエストラに関する基本理論を知っていれば、50%の人が知っています.
この問題の核心は0を考慮せず,1人の配列だけを考慮する.(コメントとしてマークされている部分はこの部分です.)

🔋ソースコード

#include <bits/stdc++.h>

#define MAX (101)
#define INF (987654321)

//arr : 배열, cost : 배열에서 해당부분에 대한 최소거리
int arr[MAX][MAX], cost[MAX][MAX];

void bfs(int M, int N, int sx, int se){
	int dx[4] = { 1, 0, 0, -1 };
	int dy[4] = { 0, 1, -1, 0 };
	std::queue<std::pair<int, int>>q;
	q.push(std::make_pair(sx, se));
	cost[0][0] = 0;
	
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i=0;i<4;++i){ //상하좌우 4방향을 차례대로 순회
			int newx = x + dx[i];
			int newy = y + dy[i];
		
			if(newx < 0 || newy < 0 || newx >= M || newy >= N ) continue;
			if(arr[newy][newx] == 1){ //오직 1일때에만 고려합니다.
            
            			//이 부분 익숙하신분 계실겁니다.
                        	//네, 다익스트라랑 매우 비슷합니다.
				if(cost[newy][newx] > cost[y][x] + 1){ /**/
					cost[newy][newx] = cost[y][x] + 1;
					q.push(std::make_pair(newx, newy));
				}
			}
		}
	}
}

int main() {
	int N, M;
	std::cin >> N >> M;
	for(int i=0;i<N;++i){
		std::string str;
		std::cin >> str;
		for(int j=0;j<M;++j){
			arr[i][j] = str[j] - '0'; //'0'을 빼는 이유는 아스키코드값에 따라 문자를 숫자로 바꾸기 위함입니다.
			cost[i][j] = INF;
		}
	}
	
	bfs(M, N, 0, 0);
    
   	//1을 더하는이유는 시작점때문입니다.
    	//시작점은 항상 1 이기때문이죠.
	std::cout << cost[N - 1][M - 1] + 1;
}

この問題はどこで出したのですか.

💉終了時..。

グラフィックアルゴリズムは面白いので、相対的に解くことが多いですが、部分的なマージ、リュックサック、ダイナミックに関連するアルゴリズムの問題は弱いので、もっと解く必要があります.