[BOJ/Python]15683号監視

68281 ワード
サムスン back tracking python boj テキストリンク

今回の問題は三星機が問題を起こし、後継追跡と実施を通じて解決したことだ.最初は背中合わせだと思っていましたが、ブルートフォスでも解決できると思い、ブルートフォスで体現しています.cctvの位置と種類をcctvsリストに移し,それを種類降順に並べ,cctvが見える区間の大きさを求め,その中の大きなフォローを実現した.
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
cctv=[[0 for _ in range(m)] for _ in range(n)]
cctvs=[]
for i in range(n):
    for j in range(m):
        if 0<grid[i][j]<6:
            cctvs.append((i, j, grid[i][j]))
            cctv[i][j]=-1
cctvs.sort(key=lambda x: x[2], reverse=True)
def monitoring(sy, sx):
    if grid[sy][sx]==1:
        cnt=[0 for _ in range(4)]
        for i in range(4):
            ny, nx=sy+dy[i], sx+dx[i]
            while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                if cctv[ny][nx]==0:
                    cnt[i]+=1
                ny+=dy[i]
                nx+=dx[i]
        d=cnt.index(max(cnt))
        ny, nx=sy+dy[d], sx+dx[d]
        while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
            cctv[ny][nx]=-1
            ny+=dy[d]
            nx+=dx[d]
    elif grid[sy][sx]==2:
        cnt=[0 for _ in range(2)]
        for i in range(2):
            ny1, nx1=sy+dy[i], sx+dx[i]
            while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
                if cctv[ny1][nx1]==0:
                    cnt[i]+=1
                ny1+=dy[i]
                nx1+=dx[i]
            ny2, nx2=sy-dy[i], sx-dx[i]
            while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
                if cctv[ny2][nx2]==0:
                    cnt[i]+=1
                ny2-=dy[i]
                nx2-=dx[i]
        d=cnt.index(max(cnt))
        ny1, nx1=sy+dy[d], sx+dx[d]
        while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
            cctv[ny1][nx1]=-1
            ny1+=dy[d]
            nx1+=dx[d]
        ny2, nx2=sy-dy[d], sx-dx[d]
        while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
            cctv[ny2][nx2]=-1
            ny2-=dy[d]
            nx2-=dx[d]
    elif grid[sy][sx]==3:
        cnt=[0 for _ in range(4)]
        for i in range(4):
            ny1, nx1=sy+dy[i], sx+dx[i]
            while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
                if cctv[ny1][nx1]==0:
                    cnt[i]+=1
                ny1+=dy[i]
                nx1+=dx[i]
            ny2, nx2=sy+dy[(i+1)%4], sx+dx[(i+1)%4]
            while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
                if cctv[ny2][nx2]==0:
                    cnt[i]+=1
                ny2+=dy[(i+1)%4]
                nx2+=dx[(i+1)%4]
        d=cnt.index(max(cnt))
        ny1, nx1=sy+dy[d], sx+dx[d]
        while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
            cctv[ny1][nx1]=-1
            ny1+=dy[d]
            nx1+=dx[d]
        ny2, nx2=sy+dy[(d+1)%4], sx+dx[(d+1)%4]
        while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
            cctv[ny2][nx2]=-1
            ny2+=dy[(d+1)%4]
            nx2+=dx[(d+1)%4]
    elif grid[sy][sx]==4:
        cnt=[0 for _ in range(4)]
        for i in range(4):
            for j in range(4):
                if i==j:
                    continue
                ny, nx=sy+dy[j], sx+dx[j]
                while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                    if cctv[ny][nx]==0:
                        cnt[i]+=1
                    ny+=dy[j]
                    nx+=dx[j]
        d=cnt.index(max(cnt))
        for i in range(4):
            if i==d:
                continue
            ny, nx=sy+dy[i], sx+dx[i]
            while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                cctv[ny][nx]=-1
                ny+=dy[i]
                nx+=dx[i]
    elif grid[sy][sx]==5:
        for i in range(4):
            ny, nx=sy+dy[i], sx+dx[i]
            while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                cctv[ny][nx]=-1
                ny+=dy[i]
                nx+=dx[i]
for y, x, _ in cctvs:
    monitoring(y, x)
answer=0
for i in range(n):
    for j in range(m):
        if grid[i][j]==0 and cctv[i][j]==0:
            answer+=1
print(answer)
しかし、17%の人が間違って答えた.見つからない反例があり、解決しようと努力したが解決しなかった.従って,決定はすべての方法を決定する後追跡で実現する.cctvを1から5まで関数で表す.cctvの利用可能な範囲は、上記のコードに沿っています.
  • cctv 1には4種類のハウジングが駆動可能である.
  • cctv 2の場合、2種類のケースで駆動できます.
  • cctv 3には4種類のハウジングが駆動可能である.
  • cctv 4には4種類のハウジングが駆動可能である.
  • cctv 5の場合、1つのハウジングで駆動することができる.
    • すべてのケースは、設定関数で遡及されます.また、idxがcctvsの長さに等しい場合には、gridとcctvをカウント関数でループし、両者が0の場合にのみカウント変数を増やして戻し、この戻り値と既存値の最大値をとる.
    これらの特徴を用いて,遡及コードを実現し,反例から脱した.

    Code

    import sys
from copy import deepcopy
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[-1, 0, 1, 0], [0, -1, 0, 1]
cctv=deepcopy(grid)
cctvs=[]
for i in range(n):
    for j in range(m):
        if 0<grid[i][j]<6:
            cctvs.append((i, j, grid[i][j]))
            cctv[i][j]=-1
def counting(cctv):
    cnt=0
    for i in range(n):
        for j in range(m):
            if grid[i][j]==0 and cctv[i][j]==0:
                cnt+=1
    return cnt
answer=sys.maxsize
def cctv1(y, x, d, tmp_cctvs):
    ny, nx=y+dy[d], x+dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[d]
        nx+=dx[d]
def cctv2(y, x, d, tmp_cctvs):
    ny, nx=y+dy[d], x+dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[d]
        nx+=dx[d]
    ny, nx=y-dy[d], x-dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny-=dy[d]
        nx-=dx[d]
def cctv3(y, x, d, tmp_cctvs):
    ny, nx=y+dy[d], x+dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[d]
        nx+=dx[d]
    ny, nx = y+dy[(d+1)%4], x+dx[(d+1)%4]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[(d+1)%4]
        nx+=dx[(d+1)%4]
def cctv4(y, x, d, tmp_cctvs):
    for i in range(4):
        if i == d:
            continue
        ny, nx=y+dy[i], x+dx[i]
        while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
            tmp_cctvs[ny][nx]=-1
            ny+=dy[i]
            nx+=dx[i]
def cctv5(y, x, tmp_cctvs):
    for i in range(4):
        ny, nx = y+dy[i], x+dx[i]
        while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
            tmp_cctvs[ny][nx]=-1
            ny+=dy[i]
            nx+=dx[i]
def setting(cctv, idx):
    global answer
    if idx==len(cctvs):
        answer=min(answer, counting(cctv))
        return
    if cctvs[idx][2]==1:
        for i in range(4):
            tmp_cctvs=deepcopy(cctv)
            cctv1(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==2:
        for i in range(2):
            tmp_cctvs=deepcopy(cctv)
            cctv2(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==3:
        for i in range(4):
            tmp_cctvs=deepcopy(cctv)
            cctv3(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==4:
        for i in range(4):
            tmp_cctvs=deepcopy(cctv)
            cctv4(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==5:
        tmp_cctvs=deepcopy(cctv)
        cctv5(cctvs[idx][0], cctvs[idx][1], tmp_cctvs)
        setting(tmp_cctvs, idx+1)
setting(cctv, 0)
print(answer)
    CPU性能テストツール-Linpack
    [TIL/220419]