実装(アルゴリズム、Python)

実装タイプ

イコールのゲーム問題
ひょうじゅんもんだい

このコセットの本を読むときのコード

この可愛いアイデアをちょっと見て書いたコード

n, m = map(int,input().split())
x, y, p = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

grid = []
for i in range(n):
    grid.append(list(map(int, input().split())))

visited = [[False for _ in range(m)] for _ in range(n)]
visited[x][y] = True
def move(x, y, p):
    mcnt = 0
    while True:
        fcnt = 0
        for i in range(4):
            print('x,y', (x, y))
            print('i', i)
            if p == 0:
                np = 3
            else:
                np = p - 1

            nx = x + dx[np]
            ny = y + dy[np]
			
            # 맵은 어차피 벽으로 사면이 둘러쌓여 있어서 a는 사실 불필요
            a = (nx<0 or nx>(n-1) or ny<0 or ny>(m-1))
            # 방문한 격자라면
            b = (visited[nx][ny] == True)
            # 벽이라면
            c = (grid[nx][ny]==1)

            if a or b or c:
                p = np # 방향만 바꾸고
                fcnt += 1 
            else:
                x = nx
                y = ny # 위치 바꾸고
                p = np # 방향 바꾸고
                visited[x][y] = True
                mcnt += 1
                break # 옮겨갔으니까 break
        if fcnt==4:
            if grid[x-dx[p]][y-dy[p]] == 1:
                print(visited)
                return mcnt
            x -= dx[p]
            y -= dy[p]

print(move(x, y, p))

この方向に進むとき、x + dx[i]を後方に移動するとき、x - dx[i]を後方に移動する

問題の実施は問題の理解にとって極めて重要である.

私たちは頭の中ですべての状況をシミュレートしなければなりません.

白俊を置いてもう一度見ると、このテストボックスだけが合格した.

ノードへの最初のアクセスを忘れないでください

flag処理が不要なのは,上のコードで方向変化の回数(fcnt)のみを計算したためである.

記憶がリセットされて白俊問題を解くコード。

n, m = map(int, input().split())
x, y, pos = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(map(int,input().split())))
visited = [[False for _ in range(m)] for _ in range(n)]
cnt = 1
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
visited[x][y] = True

while True:
    for i in range(4):
        flag = False
        if pos == 0:
            pos = 3
        else:
            pos -= 1

        nx = x + dx[pos]
        ny = y + dy[pos]
		
        # 움직일 수 있는 조건이라면
        if grid[nx][ny] != 1 and visited[nx][ny]!=True:
            visited[nx][ny] = True
            x = nx
            y = ny
            cnt += 1
            flag = True # 4번 돌았지만 위치를 옮긴 상황을 기록
            break
    if i == 3:
        if flag==True:
            continue
        elif grid[x-dx[pos]][y-dy[pos]] == 1:
            break
        else:
            x -= dx[pos]
            y -= dy[pos]
print(cnt)

for 4番ゲートですが、最後の方向に移動する可能性があるのでflagを使うことを考えます

最初のノード応答-最初のノードを考慮すると、cnt 1から週

カタツムリ問題

実施問題

操作座標

のみが移動する概念

三角形ではないNXNアレイは、インデックス

を容易に作成することができる.

特定の方向に1回回転するごとに、そのレベルの個数が1つ減少する点

.

リファレンス

n = 5
grid = [[-1 for _ in range(n)]  for _ in range(n)]
x = -1
y = n
num = 0
for i in range(n):
    for j in range(n-i):
        if i%3==0:
            x += 1
            y -= 1
        elif i%3==1:
            x -= 1
        elif i %3 == 2:
            y += 1
        num += 1
        grid[x][y] = num

# print(grid)
for i in grid:
    print(i)

サメ小学校

質問リンク

n = int(input())
num = {}
for _ in range(n**2):
    a = list(map(int, input().split()))
    num[a[0]] = a[1:]
grid = [[0 for _ in range(n)] for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in num.keys():
    # print('i', num[i][0])
    g = []
    v1 = []
    v2 = []
    if i==0:
        grid[1][1] = i
    else:
        for x in range(n):
            for y in range(n):
                if grid[x][y] == 0:
                    s = 0
                    so = 0
                    for j in range(4):
                        nx = x + dx[j]
                        ny = y + dy[j]
                        if nx < 0 or nx >(n-1) or ny<0 or ny>(n-1): # 좌표룰 벗어나지 않으면
                            continue
                        else:
                            if grid[nx][ny] in num[i]: # 친한친구면 +1
                                s += 1
                            if grid[nx][ny] == 0: # 빈자리면 +1
                                so += 1
                    g.append((x, y))
                    v1.append(s)
                    v2.append(so)

        if v1.count(max(v1)) == 1:
            x, y = g[v1.index(max(v1))]
            grid[x][y] = i
            # print('1 if', (x, y), num[i][0])
        else:
            v1_ind = []
            v2_val = []
            for p, pp in enumerate(v1):
                 if pp == max(v1):
                     v1_ind.append(p)
            for pp in v1_ind:
                v2_val.append(v2[pp])

            if v2_val.count(max(v2_val)) == 1:
                x, y = g[v1_ind[v2_val.index(max(v2_val))]]
                grid[x][y] = i
                # print('2 if', (x, y), num[i][0])
            else: # 3. 행작고 열작을수록
                x, y = g[v1_ind[v2_val.index(max(v2_val))]]
                grid[x][y] = i
                # print('2 else', (x, y), num[i][0])

all_s = 0
for x in range(n):
    for y in range(n):
        s = 0
        for ii in range(4):
            nx = x + dx[ii]
            ny = y + dy[ii]
            if nx < 0 or nx > (n - 1) or ny < 0 or ny > (n - 1):  # 좌표룰 벗어나지 않으면
                continue
            else:
                if grid[nx][ny] in num[grid[x][y]]:  # 친한친구면 +1
                    s += 1
        if s==2:
            s = 10
        elif s==3:
            s = 100
        elif s==4:
            s = 1000
        all_s += s

print(all_s)

実施問題の鍵は、問題

を正しく理解することにある.

の初期値を設定し、最大値を求める方法も考慮した.まず行、列番号が小さい場所を格納するのもいいです.

そうすれば、同じ最大値があれば解決できないかもしれないので、残しておいて、これで解くと解決します.

コードソース

import sys
from collections import defaultdict
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
N = int(input())
arr = [[0]*N for _ in range(N)]
likedict = defaultdict(list)
result = 0
 
for _ in range(N*N):
    _input = list(map(int, input().split()))
    likedict[_input[0]] = _input[1:]
    
    max_x = 0
    max_y = 0
    max_like = -1
    max_empty = -1
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 0:
                likecnt = 0
                emptycnt = 0
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < N and 0 <= ny < N:
                        if arr[nx][ny] in _input:
                            likecnt += 1
                        if arr[nx][ny] == 0:
                            emptycnt += 1
                            
                if max_like < likecnt or (max_like == likecnt and max_empty < emptycnt):
                    max_x = i
                    max_y = j
                    max_like = likecnt
                    max_empty = emptycnt
                    
    arr[max_x][max_y] = _input[0]
    
for i in range(N):
    for j in range(N):
        cnt = 0
        like = likedict[arr[i][j]]
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                if arr[nx][ny] in like:
                    cnt += 1
        if cnt != 0:
            result += 10 ** (cnt-1)
            
print(result)

友達数が既存の値より大きい場合は->その値として保存

友人数が同じ場合は->空席数が大きい場合は->その値として保存

友だち数が同じなら->空席数が同じなら->前のように

すべてのプリファレンスリストを保存する必要もありません.
入力と同時にすればいいです.

defaultdict(list)はキー値と値を指定しません.
新しいキー値を受信すると、デフォルトでは空のリストがvalueになります.