Submission #750568
Source Code Expand
# frozen_string_literal: true # Teratailの質問のコードを改変 # https://teratail.com/questions/36739 # 変えたところ # * クラス化(ただの趣味) # * 配列を1次元 # * 変数に入れて、Array#[]の呼び出しをを極力なくす class Keiro MOD = 100_000_007 def initialize(h, w, grid) @h = h @h2 = h + 2 @w = w @w2 = w + 2 # @gridと@combは1次元 @grid = grid @comb = Array.new(@h2 * @w2, nil) # @nexts = [-1, 1, -@w2, @w2] end def dfs(ij) # 動かない場合もあるのでres=1 res = 1 # 何度も呼ぶのは1度だけにする gij = @grid[ij] # 上下左右のほうが大きければ移動する # 上下左右への計算も工夫 # @nexts.each do |x| # x += ij # res += @comb[x] || dfs(x) if gij < @grid[x] # end # res += @comb[ij - 1] || dfs(ij - 1) if gij < @grid[ij - 1] # res += @comb[ij + 1] || dfs(ij + 1) if gij < @grid[ij + 1] # res += @comb[ij - @w2] || dfs(ij - @w2) if gij < @grid[ij - @w2] # res += @comb[ij + @w2] || dfs(ij + @w2) if gij < @grid[ij + @w2] x = ij - 1 res += @comb[x] || dfs(x) if gij < @grid[x] x = ij + 1 res += @comb[x] || dfs(x) if gij < @grid[x] x = ij - @w2 res += @comb[x] || dfs(x) if gij < @grid[x] x = ij + @w2 res += @comb[x] || dfs(x) if gij < @grid[x] # 移動経路数を2次元配列に格納し、値を返す # Array#[]で呼び直さない # res %= MOD @comb[ij] = res res end def dfs_each ij = @w2 + 1 @h.times do @w.times do yield (@comb[ij] || dfs(ij)) ij += 1 end ij += 2 end end end # 高さ、幅の読み取り h, w = gets.chomp.split.map(&:to_i) # マス目を格納する2次元配列及び、経路数を格納する2次元配列を用意 grid = [] # 最初 grid.concat(Array.new(w + 2, 0)) # マス目のよみとり h.times do grid << 0 grid.concat(gets.split.map(&:to_i)) grid << 0 end # 最後 grid.concat(Array.new(w + 2, 0)) keiro = Keiro.new(h, w, grid) ans = 0 keiro.dfs_each do |dfs| ans += dfs # MODより大きければ引く # ans %= Keiro::MOD # ans -= Keiro::MOD if ans > Keiro::MOD end puts(ans % Keiro::MOD)
Submission Info
Submission Time | |
---|---|
Task | D - 経路 |
User | raccy |
Language | Ruby (2.3.3) |
Score | 0 |
Code Size | 2336 Byte |
Status | TLE |
Exec Time | 2116 ms |
Memory | 115964 KB |
Judge Result
Set Name | sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample01.txt, sample02.txt |
All | 00.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, sample01.txt, sample02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00.txt | TLE | 2116 ms | 115708 KB |
01.txt | RE | 859 ms | 19964 KB |
02.txt | AC | 1606 ms | 18172 KB |
03.txt | AC | 18 ms | 1788 KB |
04.txt | AC | 18 ms | 1788 KB |
05.txt | AC | 18 ms | 1788 KB |
06.txt | AC | 19 ms | 1916 KB |
07.txt | AC | 19 ms | 1916 KB |
08.txt | AC | 18 ms | 1788 KB |
09.txt | AC | 17 ms | 1788 KB |
10.txt | AC | 22 ms | 1916 KB |
11.txt | AC | 1754 ms | 19196 KB |
12.txt | AC | 1782 ms | 19196 KB |
13.txt | AC | 1772 ms | 19196 KB |
14.txt | AC | 1798 ms | 19196 KB |
15.txt | TLE | 2112 ms | 115964 KB |
16.txt | AC | 1752 ms | 19196 KB |
17.txt | AC | 1780 ms | 19196 KB |
18.txt | AC | 1534 ms | 18172 KB |
19.txt | AC | 1444 ms | 18172 KB |
sample01.txt | AC | 17 ms | 1788 KB |
sample02.txt | AC | 18 ms | 1788 KB |