🐸

[鉄則A25] Number of Routes / [EDPC H] Grid 1

2024/04/13に公開

Ruby

左上から右下まで何通りあるか調べる DP 問題。

問題を要約する

右と下に動ける
途中に障害物がある
左上から右下までの移動は何通りあるか？

考え方

1x1 の場合

	0
0	1

左上から開始するので左上は 1 通りになる。

2x2 の場合

	0	1
0	1	1
1	1	2

(1, 1) の 2 は上の 1 と左の 1 の合計になるので 1 + 1 = 2 とする。

片方に障害物がある場合

	0	1
0	1	#
1	1	1

(1, 1) の 1 は上が障害物なので無視して左の 1 だけコピーする。

上も左も障害物がある場合

	0	1
0	1	#
1	#	0

(1, 1) の 0 は上も左も障害物なので 0 とする。

例1のマップと dp

	0	1	5	6
0			#
1
2		#		#
3	#

	0	1	2	3	4	5	6	7
0	1	1	1	1	1	1	0	0
1	1	2	3	4	5	5	5	5
2	1	3	6	4	9	14	19	5
3	1	3	3	7	16	30	30	35

障害物のあるセルが 0 になるのではない。「貰うDP」なので、貰うために参照したセルが障害物だったとき「貰わない」とするだけである。

解説の模範解答 (AC)

49 ms

H, W = gets.split.collect(&:to_i)   # => [4, 8]
C = H.times.collect { gets.strip }  # => [".....#..", "........", "..#...#.", "#......."]
dp = Array.new(H) { Array.new(W) }
H.times do |y|
  W.times do |x|
    if x == 0 && y == 0
      dp[y][x] = 1              # 左上は 1
    else
      dp[y][x] = 0
      y >= 1 && C[y - 1][x] == "." and dp[y][x] += dp[y - 1][x] # 上があれば貰う
      x >= 1 && C[y][x - 1] == "." and dp[y][x] += dp[y][x - 1] # 左があれば貰う
    end
  end
end
p dp.last.last                      # => 35

類似問題

[EDPC H] Grid 1

最後の解を指定の値で割った余りにする部分を追加しただけで解法は同じになる。

886 ms

H, W = gets.split.collect(&:to_i)   # => [20, 20]
C = H.times.collect { gets.strip }  # => ["....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "...................."]
dp = Array.new(H) { Array.new(W) }
H.times do |y|
  W.times do |x|
    if x == 0 && y == 0
      dp[y][x] = 1              # 左上は 1
    else
      dp[y][x] = 0
      y >= 1 && C[y - 1][x] == "." and dp[y][x] += dp[y - 1][x] # 上があれば貰う
      x >= 1 && C[y][x - 1] == "." and dp[y][x] += dp[y][x - 1] # 左があれば貰う
    end
  end
end
p dp.last.last.modulo(10**9 + 7)    # => 345263555

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
1	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
2	1	3	6	10	15	21	28	36	45	55	66	78	91	105	120	136	153	171	190	210
3	1	4	10	20	35	56	84	120	165	220	286	364	455	560	680	816	969	1140	1330	1540
4	1	5	15	35	70	126	210	330	495	715	1001	1365	1820	2380	3060	3876	4845	5985	7315	8855
5	1	6	21	56	126	252	462	792	1287	2002	3003	4368	6188	8568	11628	15504	20349	26334	33649	42504
6	1	7	28	84	210	462	924	1716	3003	5005	8008	12376	18564	27132	38760	54264	74613	100947	134596	177100
7	1	8	36	120	330	792	1716	3432	6435	11440	19448	31824	50388	77520	116280	170544	245157	346104	480700	657800
8	1	9	45	165	495	1287	3003	6435	12870	24310	43758	75582	125970	203490	319770	490314	735471	1081575	1562275	2220075
9	1	10	55	220	715	2002	5005	11440	24310	48620	92378	167960	293930	497420	817190	1307504	2042975	3124550	4686825	6906900
10	1	11	66	286	1001	3003	8008	19448	43758	92378	184756	352716	646646	1144066	1961256	3268760	5311735	8436285	13123110	20030010
11	1	12	78	364	1365	4368	12376	31824	75582	167960	352716	705432	1352078	2496144	4457400	7726160	13037895	21474180	34597290	54627300
12	1	13	91	455	1820	6188	18564	50388	125970	293930	646646	1352078	2704156	5200300	9657700	17383860	30421755	51895935	86493225	141120525
13	1	14	105	560	2380	8568	27132	77520	203490	497420	1144066	2496144	5200300	10400600	20058300	37442160	67863915	119759850	206253075	347373600
14	1	15	120	680	3060	11628	38760	116280	319770	817190	1961256	4457400	9657700	20058300	40116600	77558760	145422675	265182525	471435600	818809200
15	1	16	136	816	3876	15504	54264	170544	490314	1307504	3268760	7726160	17383860	37442160	77558760	155117520	300540195	565722720	1037158320	1855967520
16	1	17	153	969	4845	20349	74613	245157	735471	2042975	5311735	13037895	30421755	67863915	145422675	300540195	601080390	1166803110	2203961430	4059928950
17	1	18	171	1140	5985	26334	100947	346104	1081575	3124550	8436285	21474180	51895935	119759850	265182525	565722720	1166803110	2333606220	4537567650	8597496600
18	1	19	190	1330	7315	33649	134596	480700	1562275	4686825	13123110	34597290	86493225	206253075	471435600	1037158320	2203961430	4537567650	9075135300	17672631900
19	1	20	210	1540	8855	42504	177100	657800	2220075	6906900	20030010	54627300	141120525	347373600	818809200	1855967520	4059928950	8597496600	17672631900	35345263800