質問する

https://www.acmicpc.net/problem/15683
スタートリンクのオフィスは1です×1の大きさが正方形のN×Mサイズの長方形で表すことができます.事務室にはK個の監視カメラが設置されており、監視カメラは5種類ある.各監視カメラが監視できる方法は以下の通りです.

1番の監視は1つの方向しか監視できません.2番と3番は2つの方向を監視することができ、2番の監視の方向は反対で、3番は直角方向であるべきだ.4番は3つの方向にあり、5番は4つの方向を監視することができます.
監視カメラは、監視可能な方向にある車両全体を監視することができる.事務室には壁があり、監視カメラが壁を透過できない.監視カメラでは監視できない領域は死角地帯だそうです.
モニタカメラは回転可能で、回転は常に90度方向で、モニタする方向は横または縦である必要があります.

地図上の0はスペース、6は壁、1~5は監視カメラの番号です.上記の例では、以下に示すように、監視可能な領域を1番方向に「#」と表示しています.

モニタが壁を通過できないため、モニタ1番→方向の場合、6右側の格子をモニタできません.

上記の例では、監視可能な方向を以下に示す.

監視カメラは監視することができます.次の例です.

上記の場合、2の方向が↕3の方向←と↓の場合、監視される領域は以下の通りである.

オフィスのサイズ、ステータス、監視ビデオの情報がある場合は、監視ビデオの方向を決定し、プログラムを作成して死角の最小サイズを求めます.

入力

第1行は、オフィスの縦方向サイズNおよび横方向サイズMを与える.(1 ≤ N, M ≤ 8)
2行目からN行にオフィスの各部屋の情報が与えられる.0はスペース、6は壁、1～5はモニタリング、問題で説明したモニタリングタイプです.
監視カメラの最大数は8個を超えない.

しゅつりょく

最初の行は死角の最小サイズを出力します.

アイデア

クローン関数の考え方を参考にした.

の各中央テレビ局が見える方向の数を方向に記録します.

dfsを用いて求められるすべての数を求めた.

find関数を使用してcctvで表示できる領域を「#」とマークします.

✔¥コード説明
1.入力を受信し、cctv位置を別途取り、cctvリストに保存する.
2.表示配列と現在使用されているcctvのcntをdfs上に同時に携帯する.
3.cctvが指定した数字と同じ場合、0人領域の数字を計算します.
4.または該当するcctv番号を入力し、cctv方向の領域を「#」に変更します.
5.cctvの方向を設定し、次のcctvの方向を決定してdfs関数を呼び出す.
6.cctvの個数で方向を決めたら、戻り、tmpは前の状態に戻ります.

[#Error]私のコードpython

혼자 풀려고 하다가 못 풀었다. 아직 dfs를 잘 구현하지 못하는 것 같다.

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]

d = [[-1, 0], [1, 0], [-1, 0], [0, -1]] #상하좌우
direction = [[],
             [[0], [1], [2], [3]],
             [[0, 2], [1, 3]],
             [[0, 1], [1, 2], [2, 3], [3, 0]],
             [[1, 2, 3], [0, 2, 3], [0, 1, 3], [0, 1, 2]],
             [[0, 1, 2, 3]]]

def find(x, y, dx, dy):
    tmp = []
    while 0 <= x+dx < n and 0 <= y+dy <m:
        x += dx
        y += dy
        if arr[x][y] == 6:
            break
        tmp.append([x, y])
    return tmp


cctv = []
w = []
for i in range(n):
    for j in range(m):
        if arr[i][j] in range(1, 6):
            cctv.append([arr[i][j], i, j])
        elif arr[i][j] == 6:
            w.append([i, j])

[#Clone]関数py 3

clone함수 참고해서 다시 혼자 해봤는데 dfs는 아직 어려운 것 같다.

pythonでタイムアウトしました.pypy 3をコミットしてから通過します.

import copy

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]
d = [[-1, 0], [0, -1], [1, 0], [0, 1]]  #상, 좌, 하, 우
directions = [[],
              [[0], [1], [2], [3]],
              [[0, 2], [1, 3]],
              [[0, 1], [1, 2], [2, 3], [3, 0]],
              [[1, 2, 3], [0, 2, 3], [0, 1, 3], [0, 1, 2]],
              [[0, 1, 2, 3]]
              ]


def find(x, y, direction, arrc):
    for k in direction:
        nx = x
        ny = y
        while 0 <= nx+d[k][0] < n and 0 <= ny+d[k][1] < m:
            nx += d[k][0]
            ny += d[k][1]
            if arrc[nx][ny] != 6:
                if arrc[nx][ny] == 0:
                    arrc[nx][ny] = '#'
            else:
                break


def dfs(a, cnt):
    global ans
    tmp = copy.deepcopy(a)
    if cnt == len(cctv):
        c = 0
        for i in range(len(tmp)):
            c += tmp[i].count(0)
        ans = min(ans, c)
        return
    cc, x, y = cctv[cnt]
    for i in range(len(directions[cc])):
        find(x, y, directions[cc][i], tmp)
        dfs(tmp, cnt+1)
        tmp = copy.deepcopy(a)


ans = 9999
cctv = []
for i in range(n):
    for j in range(m):
        if arr[i][j] in range(1, 6):
            cctv.append([arr[i][j], i, j])
dfs(arr, 0)
print(ans)

クローン関数のソース