研究所

アイデア
組み合わせ

Mウイルス

で作成されたウイルスの組合せを使用して、bfs

をそれぞれ参照します.
実施方法

組合せ

シーケンスを作成するときの関数を変形することにより

を作成する.

bfs

dequeに時間情報を含む

アクセス時

Time情報を表示

アクセス表示の理由は、

Time check

最短時間で到着できない場所がある場合false出力

難点

TimeCheck関数は,maxが0の場合,戻り値がfalseに等しく,異なる答えが得られると考えている.

max+1を返し、false trueを外で判断し、-1スケール

Pythonはfalseを0と認識

コンビネーション中でないウイルスに遭遇した場合,通常のように探索は行われないと考えられる.

ウイルスは壁として認識されているため、後ろを進むことができればナビゲーションできません.

ウイルスを通過すると時間情報は+1,アクセスすると0をウイルスとする

アクセスの0がウイルスの場所としてマークされているため、アクセスポイントと非アクセスポイントを区別するために-1に初期化されます.

コード#コード#

python

from _collections import deque


def find():
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 2:
                virus.append((i,j))

def combination(index):
    if index == M:
        temp = a[:]
        comb.append(temp)
    else:
        in_perm = [False]*n
        for i in range(index):
            in_perm[a[i]] = True
        for i in range(n-1,-1,-1):
            if in_perm[i]:
                posi = i + 1
                break
        else:
            posi = 0
        c = [0] * n
        cnt = 0
        for i in range(posi,n):
            if not in_perm[i]:
                c[cnt] = i
                cnt += 1
        for i in range(cnt):
            a[index] = c[i]
            combination(index+1)

def time_check():
    max = -1
    isSuccess = True
    for y in range(N):
        for x in range(N):
            if visited[y][x] > max:
                max = visited[y][x]
            elif visited[y][x] == -1 and not matrix[y][x]:
                isSuccess = False
    if isSuccess:
        return max+1
    else:
        return isSuccess

def bfs():
    while deq:
        here = deq.popleft()
        y, x, time = here[0], here[1], here[2]
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and matrix[ny][nx] == 2 and visited[ny][nx] == -1:
                deq.append((ny,nx,time+1))
                visited[ny][nx] = 0
            elif 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and visited[ny][nx] == -1:
                deq.append((ny,nx,time+1))
                visited[ny][nx] = time+1

direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(N)]
virus = []
find()
n = len(virus)
a = [0] * M
comb = []
combination(0)
min = 987654321
isFail = True
for idx in range(len(comb)):
    deq = deque()
    visited = [[-1]*N for _ in range(N)]
    for i in range(M):
        y,x = virus[comb[idx][i]][0],virus[comb[idx][i]][1]
        deq.append((y,x,0))
        visited[y][x] = 0
    bfs()
    ans = time_check()
    if ans and ans-1 < min:
        min = ans-1
        isFail = False
else:
    if isFail:
        print(-1)
    else:
        print(min)

java

import java.util.*;
import java.io.*;

public class Main17142_연구소3 {
	static int N, M;
	static int[][] matrix;
	static int[][] direct = {
			{-1,0},
			{0,1},
			{1,0},
			{0,-1},
	};
	static int[][] comb;
	static int[] a;
	static int[][] virus;
	static int virusCount = 0;
	static int top = 0;
	static int[][] visited;
	static Queue<int[] > q;
	
	public static void combination(int index, int[] a) {
		if (index == M) {
			int[] temp = new int[M];
			for (int i=0; i<M; i++) {
				temp[i] = a[i];
			}
			for (int i=0; i<M; i++) {
				comb[top][i] = temp[i];
			}
			top ++;
		} else {
			int posi = 0;
			int cnt = 0;
			boolean[] inComb = new boolean[virusCount];
			for (int i=0; i<index; i++) {
				inComb[a[i]] = true;
			}
			for (int i=virusCount-1; i>-1; i--) {
				if (inComb[i]) {
					posi = i+1;
					break;
				}
			}
			int[] c = new int[virusCount];
			for (int i=posi; i<virusCount; i++) {
				if (!inComb[i]) {
					c[cnt] = i;
					cnt ++;
				}
			}
			for (int i=0; i<cnt; i++) {
				a[index] = c[i];
				combination(index+1, a);
			}
			
		}
	}
	
	public static void bfs() {
		int y, x, ny, nx, time;
		while (!q.isEmpty()) {
			int[] here = q.poll();
			time = here[2];
			for (int dir=0; dir<4; dir++) {
				ny = here[0] + direct[dir][0];
				nx = here[1] + direct[dir][1];
				if (0 <= ny && ny < N && 0 <= nx && nx < N && matrix[ny][nx] == 2 && visited[ny][nx] == -1) {
					q.offer(new int[] {ny,nx,time+1});
					visited[ny][nx] = 0;
				} else if (0 <= ny && ny < N && 0 <= nx && nx < N && matrix[ny][nx] == 0 && visited[ny][nx] == -1) {
					q.offer(new int[] {ny,nx,time+1});
					visited[ny][nx] = time + 1;
				}
			}
		}
	}
	
	public static int timeCheck() {
		int max = -1;
		boolean isSuccess = true;
		for (int r=0; r<N; r++) {
			for (int c=0; c<N; c++) {
				if (visited[r][c] > max) {
					max = visited[r][c];
				} else if (visited[r][c] == -1 && matrix[r][c] == 0) {
					isSuccess = false;
					max = -1;
					break;
				}
			}
			if (!isSuccess) {
				break;
			}
		}
		return max;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		matrix = new int[N][N];
		virus = new int[10][2];
		int y, x, ans;
		int min = 987654321;
		
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
				if (matrix[i][j] == 2) {
					virus[virusCount][0] = i;
					virus[virusCount][1] = j;
					virusCount ++;
				}
			}
		}
		
		comb = new int[10000][M];
		a = new int[M];
		combination(0, a);
		
		for (int i=0; i<top; i++) {
			q = new LinkedList<>();
			visited = new int[N][N];
			for (int r=0; r<N; r++) {
				for (int c=0; c<N; c++) {
					visited[r][c] = -1;
				}
			}
			for (int j=0; j<M; j++) {
				y = virus[comb[i][j]][0];
				x = virus[comb[i][j]][1];
				q.offer(new int[] {y,x,0});
			}
			bfs();
			ans = timeCheck();
			if (ans > -1 && ans < min) {
				min = ans;
			}
		}
		if (min==987654321) {
			System.out.println(-1);
		} else {
			System.out.println(min);
		}
	}

}