[programmers]通学路
問題の説明
持続的な豪雨が一部の地域を水没させた.水没していない地域を通って学校に行きたいです.家から学校までの道はm×nサイズのグリッドで表すことができます.
下図はm=4,n=3である.
最左上隅(すなわち家屋の所在地の座標)は(1,1)であり、最右下角(すなわち学校の所在地の座標)は(m,n)である.
グリッドサイズm、n、および水没領域座標を含む2 Dフラットピットにパラメータ化します.右側と下側だけに移動し、家から学校までの最短パスの数を1000000 7で割ってからソリューション関数に戻ってください.
せいげんじょうけん
-mとnがともに1の場合、入力は与えられません.
ソースコード
#include <string>
#include <vector>
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
int answer = 0;
int map[101][101] = {0, };
int d[101][101]; // 최단 경로 저장할 배열
// 물이 잠긴 지역 -1로 표시
for(int i=0;i<puddles.size();i++) {
map[puddles[i][1]][puddles[i][0]] = -1;
}
d[1][0] = 1; // 시작은 1
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
// 물이 잠긴 곳은 갈 수 없으므로 0
if(map[i][j] == -1) d[i][j] = 0;
// 최단 경로 수 = 왼쪽, 위쪽의 경로 수의 합
else d[i][j] = (d[i-1][j]+d[i][j-1]) % 1000000007;
}
}
answer = d[n][m];
return answer;
}Reference
この問題について([programmers]通学路), 我々は、より多くの情報をここで見つけました https://velog.io/@minwest/Programmers-등굣길テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol