programming

AtCoder Beginner Contest 183 E - Queen on Grid

ABC183 E - Queen on Grid

You can share this article with

็ดฏ็ฉๅ’Œใงๆทปๅญ—ใŒใ„ใคใ‚‚ใ‚ใ‹ใ‚‰ใชใใชใ‚‹

ใจใ‚Šใ‚ใˆใšใ€่งฃ่ชฌACใ—ใŸใ‚‚ใฎใฎๅŒๆง˜ใฎๅ•้กŒใŒๆœฌ็•ชใงๅ‡บใฆใ‚‚ๆทปๅญ—ใ‚’ใƒใ‚ฐใ‚Šๆ•ฃใ‚‰ใ‹ใ™่‡ชไฟกใŒใ‚ใ‚‹ใฎใงใ€ๅฏพ็ญ–ใ‚’่€ƒใˆใŸใ„ใ€‚

่งฃ่ชฌACใ‚ณใƒผใƒ‰

h,w=map(int,input().split())
s=[input() for _ in range(h)]
MOD=10**9+7

# DP table(1-index)
dp=[[0]*(w+1) for _ in range(h+1)]
# cum sum
bot=[[0]*(w+1) for _ in range(h+1)]
rig=[[0]*(w+1) for _ in range(h+1)]
bor=[[0]*(w+1) for _ in range(h+1)]

# cum sum: 0 to (N-1) => 0 to N
for i in range(1,h+1):
  for j in range(1,w+1):
    # start position is 1
    if i==j==1: dp[i][j]=1
    # add cumsum to dp table each dir
    dp[i][j]+=(bot[i-1][j])%MOD
    dp[i][j]+=(rig[i][j-1])%MOD
    dp[i][j]+=(bor[i-1][j-1])%MOD
    # can get new cumsum from current new dp
    bot[i][j]+=dp[i][j]+bot[i-1][j]
    rig[i][j]+=dp[i][j]+rig[i][j-1]
    bor[i][j]+=dp[i][j]+bor[i-1][j-1]
    # reset value to 0 at wall position
    if s[i-1][j-1]=='#':
      dp[i][j]=0
      bot[i][j]=0
      rig[i][j]=0
      bor[i][j]=0
    # get MOD
    dp[i][j]%=MODs

# output
print(dp[h][w])

ๅ›ณ่งฃ

ไธ‹ๅ›ณใฎ(i,j)(i,j)ใซใ‚ฏใ‚คใƒผใƒณใŒ่‡ณใ‚‹็ตŒ่ทฏใ‚’่€ƒใˆใ‚‹ใ€‚ใƒใƒ„ๅฐใฏๅฃใ‚’่กจใ—ใฆใ„ใ‚‹ใ€‚

img

ใ‚ฏใ‚คใƒผใƒณใฏ็›ด็ทš็š„ใซใ—ใ‹็งปๅ‹•ใงใใชใ„ใŸใ‚ใ€ๆ–นๅ‘ๅˆฅใซ้’ใƒป่ตคใƒป็ท‘ใฎใ„ใšใ‚Œใ‹ใฎไฝ็ฝฎใ‹ใ‚‰็งปๅ‹•ใ—ใฆใใ‚‹ใ“ใจใซใชใ‚‹ใ€‚

ใ“ใ‚Œใ‚’ๅ…ฌๅผ่งฃ่ชฌใจๅŒๆง˜ใฎDPๅผใง่กจใ›ใฐใ€ไปฅไธ‹ใจใชใ‚‹ใ€‚

dp[i][j]=dp[iโˆ’1][j]+dp[iโˆ’2][j]+dp[i][jโˆ’1]+dp[i][jโˆ’2]+dp[iโˆ’1][jโˆ’1]+dp[iโˆ’2][jโˆ’2]\begin{aligned} dp[i][j]&=dp[i-1][j]+dp[i-2][j]\\ &+dp[i][j-1]+dp[i][j-2]\\ &+dp[i-1][j-1]+dp[i-2][j-2] \end{aligned}

ใ“ใ‚Œใ‚’ไธ€่ˆฌๅŒ–ใ—ใฆ่กจ่จ˜ใ™ใ‚Œใฐใ€ๅณ่พบใ‚’ไปฅไธ‹ใฎ3้ …ใซใพใจใ‚ใ‚‹ใ“ใจใŒใงใใ‚‹ใ€‚

dp[i][j]=โˆ‘k=1dp[iโˆ’k][j]+โˆ‘k=1dp[i][jโˆ’k]+โˆ‘k=1dp[iโˆ’k][jโˆ’k]\begin{aligned} dp[i][j]&=\sum_{k=1}{dp[i-k][j]}\\ &+\sum_{k=1}{dp[i][j-k]}\\ &+\sum_{k=1}{dp[i-k][j-k]} \end{aligned}

ๆœ€ๅˆใซๅฃใŒใชใ„ใ‚ฑใƒผใ‚นใ‚’่€ƒใˆใ‚‹

ๅฃใŒใชใ„ใ‚ฑใƒผใ‚นใ‚’่€ƒใˆใ‚Œใฐใ€ๅ…ˆใปใฉใฎๅผใฎๅณ่พบๅ„้ …ใฏ็ดฏ็ฉๅ’Œใฎๅฝขใ‚’ใ—ใฆใ„ใ‚‹ใ€‚
ไปฃ่กจใจใ—ใฆ็ธฆๆ–นๅ‘ใ€ใ™ใชใ‚ใกbottomใซๅ‘ใ‹ใ†็ดฏ็ฉๅ’Œcum_botใ‚’่€ƒใˆใฆใฟใ‚ˆใ†ใ€‚

ใ“ใ“ใงใ€cumbot[i][j]cum_{bot}[i][j]ใฎๆทปๅญ—ใ‚’ใฉใ†็ฝฎใใ‹ใŒใƒใ‚ฐใ‚Šๆ•ฃใ‚‰ใ‹ใ—ใƒใ‚คใƒณใƒˆใ ใ€‚
่ฉฆใ—ใซใƒžใ‚น(i,j)(i,j)ใฎๅ€คใ‚’ๅซใ‚€็ดฏ็ฉๅ’Œใจใ—ใฆๆ›ธใ„ใฆใฟใ‚‹ใ€‚

cumbot[i][j]=โˆ‘k=1dp[iโˆ’k][j]=cumbot[iโˆ’1][j]+dp[i][j]\begin{aligned} cum_{bot}[i][j]&=\sum_{k=1}{dp[i-k][j]}\\ &=cum_{bot}[i-1][j]+dp[i][j] \end{aligned}

ใ“ใฎๅฝขใฏใ€ๅ…ˆใปใฉใฎ่งฃ่ชฌACใซๆบ–ๆ‹ ใ—ใŸๆทปๅญ—ใฎๅ–ใ‚Šๆ–นใงใ‚ใ‚‹ใ€‚

ๅŒบ้–“ๅ’Œใ‚’ๆฑ‚ใ‚ใ‚‹ๅ ดๅˆใฏๅŠ้–‹ๅŠ้–‰ๅŒบ้–“ใŒๅŸบๆœฌ

้€šๅธธใ€็ดฏ็ฉๅ’Œใ‚’ๆ‰ฑใ†ๅ ดๅˆใฏๅŒบ้–“ๅ’Œใ‚’ๆฑ‚ใ‚ใŸใ„ๅ ดๅˆใŒๅคšใ„ใ€‚ใใ†ใ—ใŸใจใใฏๅŠ้–‹ๅŠ้–‰ๅŒบ้–“ใง

cum[a,b)=cum[0,b)โˆ’cum[0,a)cum[a,b)=cum[0,b)-cum[0,a)

ใจใ„ใ†ใ‚ˆใ†ใซๆŒใคใฎใŒๆ•ดๅˆๆ€งใŒๅ–ใ‚Œใฆใ„ใฆไพฟๅˆฉใ ใ€‚

ใ™ใชใ‚ใก่ฆ็ด ๆ•ฐNNใฎ้…ๅˆ—[0,Nโˆ’1)[0,N-1)ใซๅฏพใ—ใฆใ€่ฆ็ด ๆ•ฐN+1N+1ใฎ็ดฏ็ฉๅ’Œ[0,N)[0,N)ใ‚’่€ƒใˆใ‚‹ๅฟ…่ฆใŒใ‚ใ‚‹ใ€‚

ใพใŸใ€ใ“ใฎใจใๅŒบ้–“[0,0)[0,0)ใฎๅ€คใฏ00ใงใ‚ใ‚‹ใ€‚

ๆœฌๅ•้กŒใซๅŒใ˜่€ƒใˆใ‚’้ฉ็”จใ™ใ‚‹

0ใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใจ1ใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใŒๅ…ฅใ‚Šไบคใ˜ใ‚‹ใจ้ ญใŒใƒใ‚ฐใ‚Šๆ•ฃใ‚‰ใ‹ใ—ใฆๆญปใ‚“ใงใ—ใพใ†ใŸใ‚ใ€ใฉใฎใ‚ˆใ†ใชๅ•้กŒใ‚’่งฃใๅ ดๅˆใงใ‚‚ๅฟ…ใš0ใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใง่€ƒใˆใ‚‹ใ“ใจใซใ—ใŸใ„ใ€‚

ใ“ใฎใจใใ€dp[i][j]dp[i][j]ใฏใƒžใ‚น(i,j)(i,j)ใซ่‡ณใ‚‹็ตŒ่ทฏๆ•ฐใจใŠใ“ใ†ใ€‚ใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใฎๅค‰ๅ‹•ใซใ‚ˆใ‚‹DPๅผใฎๅค‰ๅŒ–ใฏใชใ„ใ€‚ๅ•้กŒใฏ็ดฏ็ฉๅ’Œใจใฎๆ•ดๅˆๆ€งใฎ้ƒจๅˆ†ใงใ‚ใ‚‹ใ€‚

็ดฏ็ฉๅ’Œใฎ้…ๅˆ—ใ‚ตใ‚คใ‚บใฏๅ…ƒใจใชใ‚‹้…ๅˆ—ใฎ่ฆ็ด ๆ•ฐNNใซๅฏพใ—ใฆN+1N+1ใงใ‚ใ‚‹ใฎใงใ€ๅ…ˆใปใฉใจใฏ็•ฐใชใ‚Šcum[i][j]cum[i][j]ใฏใƒžใ‚น(i,j)(i,j)ใ‚’ๅซใพใชใ„ใ‚ˆใ†ใซๅ–ใ‚‹ใฎใŒใ‚ปใ‚ชใƒชใƒผใจ่จ€ใˆใ‚‹ใ ใ‚ใ†ใ€‚

ใ™ใชใ‚ใกใ€bottom: bot, right: rig, bottom-right: borใจใ—ใฆใ€ไปฅไธ‹ใฎใ‚ˆใ†ใซๆ›ธใ‘ใ‚‹ใ€‚

dp[i][j]=cumbot[i][j]+cumrig[i][j]+cumbor[i][j]dp[i][j]=cum_{bot}[i][j]+cum_{rig}[i][j]+cum_{bor}[i][j]

ใใ—ใฆใ€dp[i][j]dp[i][j]ใŒๆฑ‚ใพใฃใŸใจใใซๆ–ฐใŸใซๆฑ‚ใ‚ใ‚‹็ดฏ็ฉๅ’Œใฏไปฅไธ‹ใฎใ‚ˆใ†ใซใชใ‚‹ใ€‚

cumbot[i+1][j]=dp[i][j]+cumbot[i][j]cumrig[i][j+1]=dp[i][j]+cumrig[i][j]cumbor[i+1][j+1]=dp[i][j]+cumbor[i][j]cum_{bot}[i+1][j]=dp[i][j]+cum_{bot}[i][j]\\ cum_{rig}[i][j+1]=dp[i][j]+cum_{rig}[i][j]\\ cum_{bor}[i+1][j+1]=dp[i][j]+cum_{bor}[i][j]\\

ๆทปๅญ—ใ‚’ใ‚ปใ‚ชใƒชใƒผ้€šใ‚Šใซใ—ใฆ่งฃใ็›ดใ—ใŸใ‚ณใƒผใƒ‰

h,w=map(int,input().split())
s=[input() for _ in range(h)]
MOD=10**9+7

# DP table[0,N)
dp=[[0]*w for _ in range(h)]

# cumsum[0,N+1)
bot=[[0]*(w+1) for _ in range(h+1)]
rig=[[0]*(w+1) for _ in range(h+1)]
bor=[[0]*(w+1) for _ in range(h+1)]

# start position is 1
dp[0][0]=1

for i in range(h):
  for j in range(w):
    # add cumsum to dp table each dir
    dp[i][j]+=bot[i][j]%MOD
    dp[i][j]+=rig[i][j]%MOD
    dp[i][j]+=bor[i][j]%MOD
    # get MOD
    dp[i][j]%=MOD
    # now can get new cumsum from current new dp
    bot[i+1][j]+=dp[i][j]+bot[i][j]
    rig[i][j+1]+=dp[i][j]+rig[i][j]
    bor[i+1][j+1]+=dp[i][j]+bor[i][j]
    # reset value at next to wall position
    if s[i][j]=='#':
      dp[i][j]=0
      bot[i+1][j]=0
      rig[i][j+1]=0
      bor[i+1][j+1]=0

# output
print(dp[h-1][w-1])

ใ“ใ‚Œใงใ‚ˆใ†ใ‚„ใใ€ใ‚ปใ‚ชใƒชใƒผ้€šใ‚Šใฎใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใง้ ญใจใ‚ณใƒผใƒ‰ใ‚’ๆ•ด็†ใ™ใ‚‹ใ“ใจใŒใงใใŸใ€‚

ใ“ใ†ใ‚„ใฃใฆ้…ใ‚‹DPใงๆ›ธใ„ใฆใ€ใ‹ใค้…ๅˆ—ๅค–ๅ‚็…งใ‚’ifๆ–‡ใซ้ ผใ‚‰ใšใ‚„ใ‚‹ใจใ„ใ†ใฎใฏใ€ใ„ใ–ๆœฌ็•ชใงๆ›ธใใจๆœฌๅฝ“ใซใƒใ‚ฐใ‚Šๆ•ฃใ‚‰ใ‹ใ—ใฆใ—ใพใ†ใฎใง็ทด็ฟ’ใ‚ใ‚‹ใฎใฟใ ใ‚ใ†ใ€‚