ペアプログラマカード

質問する

コード#コード#

python

from itertools import permutations
from collections import defaultdict, deque
from copy import deepcopy

d = [[0, 1], [0, -1], [1, 0], [-1, 0]]


def bfs(cy, cx, ty, tx, board):
    q = deque()
    q.append((cy, cx))
    dist = [[0]*4 for _ in range(4)]
    dist[cy][cx] = 1
    while q:
        y, x = q.popleft()

        for dy, dx in d:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < 4 and 0 <= nx < 4:
                if dist[ny][nx] == 0:
                    dist[ny][nx] = dist[y][x]+1
                    q.append((ny, nx))

                if dy == 0:
                    while 0 <= nx < 4 and board[ny][nx] == 0:
                        nx += dx
                    if not 0 <= nx < 4:
                        nx -= dx
                else:
                    while 0 <= ny < 4 and board[ny][nx] == 0:
                        ny += dy
                    if not 0 <= ny < 4:
                        ny -= dy
                if dist[ny][nx] == 0:
                    dist[ny][nx] = dist[y][x]+1
                    q.append((ny, nx))
    return dist[ty][tx]


def dfs(y, x, d, cost, board, arr):
    global answer
    if d == len(pos):

        answer = min(answer, cost)
        return
    temp = deepcopy(board)
    y1, x1 = pos[arr[d]][0]
    y2, x2 = pos[arr[d]][1]
    v1 = bfs(y, x, y1, x1, temp)+bfs(y1, x1, y2, x2, temp)
    v2 = bfs(y, x, y2, x2, temp)+bfs(y2, x2, y1, x1, temp)

    temp[y1][x1] = 0
    temp[y2][x2] = 0
    dfs(y2, x2, d+1, cost+v1, temp, arr)
    dfs(y1, x1, d+1, cost+v2, temp, arr)


def solution(board, r, c):

    global pos, answer
    answer = 1e9
    pos = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j] == 0:
                continue
            pos[board[i][j]].append((i, j))

    for arr in list(permutations(range(1, len(pos)+1), len(pos))):
        dfs(r, c, 0, 0, board, arr)

    return answer

cpp

#include <string>
#include <vector>
#include<algorithm>
#include <queue>

using namespace std;
int maxV = 0;
vector<int> answers;
int visit[7] = { 0, };
vector<vector<int>> location[7];


int bfs(int r, int c, int r1, int c1, vector<vector<int>> board) {
    int result = 0;
    vector<vector<int>> map(4, vector<int>(4, 0));
    map[r][c] = 1;

    queue<pair<int, int>> q;
    q.push({ r,c });
    int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
      
        for (int i = 0; i < 4; i++) { //동서남북 방향키 1씩 움직이는 상황 
            int tY = y+ dir[i][0];
            int tX = x+ dir[i][1];
            if (0 > tY || tY >= 4 || 0 > tX || tX >= 4 || map[tY][tX] != 0) continue;
            map[tY][tX] = map[y][x] + 1;
            q.push({ tY,tX });
        }
        for (int i = 0; i < 4; i++) { //동서남북 컨트롤 + 방향키로 움직이는 상황 
            int tY = y;
            int tX = x;
            while (0 <= tY && tY < 4 && 0 <= tX && tX < 4) {
                tY += dir[i][0];
                tX += dir[i][1];
                if (!(0 <= tY && tY < 4 && 0 <= tX && tX < 4)||board[tY][tX] != 0) break;
            }
            
            if (!(0 <= tY && tY < 4 && 0 <= tX && tX < 4)) {
                tY -= dir[i][0];
                tX -= dir[i][1];
            }
            
             if (map[tY][tX]!=0)continue;
            map[tY][tX] = map[y][x] + 1;
            q.push({ tY,tX });
        }

    }

    
    return map[r1][c1] - map[r][c];
}

void dfs(int d, int sum, int r, int c, vector<vector<int>> board) {
    if (d == maxV) {
        answers.push_back(sum);
        return;
    }
    for (int i = 1; i <= maxV; i++) {
        if (visit[i] == 1) continue;
        visit[i] = 1;
        int b1_y = location[i][0][0];
        int b1_x = location[i][0][1];
        int b2_y = location[i][1][0];
        int b2_x = location[i][1][1];
        int value1=bfs(r, c, b1_y, b1_x, board) + bfs(b1_y, b1_x, b2_y, b2_x, board) + 2;
        int value2=bfs(r, c, b2_y, b2_x, board) + bfs(b2_y, b2_x, b1_y, b1_x, board) + 2;
        vector<vector<int>> temp = board;
        temp[b1_y][b1_x] = 0;
        temp[b2_y][b2_x] = 0;

        dfs(d + 1, sum + value1, b2_y, b2_x, temp);
        dfs(d + 1, sum + value2, b1_y, b1_x, temp);
        visit[i] = 0;
    }
}

int solution(vector<vector<int>> board, int r, int c) {
    int answer = 0;
   
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (board[i][j] != 0) {
                location[board[i][j]].push_back({ i,j });
                maxV = max(maxV, board[i][j]);
            }
        }
    }
    dfs(0, 0, r, c, board);
    answer=*min_element(answers.begin(), answers.end());
    return answer;
}

に答える