[BOJ/Python]14890号スロープ

32167 ワード
サムスン python boj テキストリンク

今回の問題は三星の寄付問題で、条件を考慮して解決した.確認カラムの関数chk columnと確認の低い関数chk rowを記述した.
  • は、下から上へ、DPにより連続個数をDP 1に記憶する.
  • から上下に、DPにより連続する個数がDP 2に記憶される.
  • 下から上へ、隣接値と比較して1の差がある場合は、dp 1とlを用いて比較し、その位置にスロープが建設されていない場合はスロープを作成する.
  • から上下に隣接値と比較して1つの相違がある場合、dp 2とlを用いて比較し、その位置に傾斜が建設されていない場合、傾斜を作成する.
    • column,rowに対してそれぞれこの方式を実現し,解決した.これは問題を解く過程で方向が混乱して長い時間がかかった問題です.

    Code

    n, l=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
answer=0
def chk_column():
    global answer
    g=[[0 for _ in range(n)] for _ in range(n)]
    dp1=[[1 for _ in range(n)] for _ in range(n)]
    dp2=[[1 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n-2, -1, -1):
            if grid[j][i]==grid[j+1][i]:
                dp1[j][i]=dp1[j+1][i]+1
        for j in range(1, n):
            if grid[j][i]==grid[j-1][i]:
                dp2[j][i]=dp2[j-1][i]+1
    for i in range(n):
        chk=True
        for j in range(n-2, -1, -1):
            if grid[j+1][i]+1==grid[j][i]:
                if dp1[j+1][i]<l:
                    chk=False
                    break
                elif dp1[j+1][i]>=l:
                    c=True
                    for k in range(l):
                        if g[j+1+k][i]>=1:
                            c=False
                            break
                    if c:
                        for k in range(l):
                            g[j+1+k][i]+=1
                    else:
                        chk=False
                        break
            if abs(grid[j+1][i]-grid[j][i])>1:
                chk=False
                break
        if not chk:
            continue
        for j in range(1, n):
            if grid[j-1][i]+1==grid[j][i]:
                if dp2[j-1][i]<l:
                    chk=False
                    break
                elif dp2[j-1][i]>=l:
                    c=True
                    for k in range(l):
                        if g[j-1-k][i]>=1:
                            c=False
                            break
                    if c:
                        for k in range(l):
                            g[j-1-k][i]+=1
                    else:
                        chk=False
                        break
        if chk:
            answer+=1
def chk_row():
    global answer
    g=[[0 for _ in range(n)] for _ in range(n)]
    dp1=[[1 for _ in range(n)] for _ in range(n)]
    dp2=[[1 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n-2, -1, -1):
            if grid[i][j]==grid[i][j+1]:
                dp1[i][j]=dp1[i][j+1]+1
        for j in range(1, n):
            if grid[i][j]==grid[i][j-1]:
                dp2[i][j]=dp2[i][j-1]+1
    for i in range(n):
        chk=True
        for j in range(n-2, -1, -1):
            if grid[i][j+1]+1==grid[i][j]:
                if dp1[i][j+1]<l:
                    chk=False
                    break
                elif dp1[i][j+1]>=l:
                    c=True
                    for k in range(l):
                        if g[i][j+1+k]>=1:
                            c=False
                            break
                    if c:
                        for k in range(l):
                            g[i][j+1+k]+=1
                    else:
                        chk=False
                        break
            if abs(grid[i][j+1]-grid[i][j])>1:
                chk=False
                break
        if not chk:
            continue
        for j in range(1, n):
            if grid[i][j-1]+1==grid[i][j]:
                if dp2[i][j-1]<l:
                    chk=False
                    break
                elif dp2[i][j-1]>=l:
                    c=True
                    for k in range(l):
                        if g[i][j-1-k]>=1:
                            c=False
                            break
                    if c:
                        for k in range(l):
                            g[i][j-1-k]+=1
                    else:
                        chk=False
                        break
        if chk:
            answer+=1
chk_column()
chk_row()
print(answer)
    SpringSecurityプローブ
    EduCoder Javaプログラミング-演算子と式第1関門:算数演算子第4関門:三元演算子