#백준_17142 연구소 3 - Java 자바

# 유형 : 탐색(BFS+DFS)

# 난이도 : 골드 4

# 주어진 바이러스 중 m개를 선택하는 것을 DFS 로, 선택한 M개의 바이러스를 퍼뜨리는 것을 BFS로 구현하면 된다.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p17142 {
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int N,M,minValue = Integer.MAX_VALUE;
    static int arr[][];
    static ArrayList<Point> arrList = new ArrayList<>();
    static ArrayList<Integer> tmpList = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                //0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 2) {
                    arrList.add(new Point(j,i));
                }
            }
        }
        for(int i=0; i<arrList.size(); i++) {
            tmpList = new ArrayList<>();
            tmpList.add(i);
            comb(i);
        }
        
        if(minValue == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(minValue);
        
    }
    private static void comb(int index) {
        if(tmpList.size() == M) {
            int result = bfs();
            if(result != -1 && minValue > result)
                minValue = result;
        }else {
            for(int v=index+1; v<arrList.size(); v++) {
                tmpList.add(v);
                comb(v);
                tmpList.remove(tmpList.size()-1);
            }
        }
    }
    public static boolean isPossible(int cp[][]) {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(cp[i][j] == 0)
                    return false;
            }
        }
        return true;
    }
    private static int bfs() {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
        
        for(int i=0; i<M; i++) {
            int index = tmpList.get(i);
            queue.add(new Point(arrList.get(index).x , arrList.get(index).y));
        }
        int result=0;
        int temp=0;
        int cpArr[][] = new int[N+1][N+1];
        boolean visit[][] = new boolean[N+1][N+1];
        for(int i=1; i<=N; i++) {
            cpArr[i] = arr[i].clone();
        }
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            boolean near = false;
            for(int i=0; i<size; i++) {
                Point po = queue.poll();
                int x = po.x;
                int y = po.y;
                
                visit[y][x] = true;
                
                for(int d=0; d<4; d++) {
                    int newX = x + moveX[d];
                    int newY = y + moveY[d];
                    
                    if(1<=newX && newX<=N && 1<=newY && newY<=N) {
                        if(!visit[newY][newX]) {
                            visit[newY][newX] = true;
                            if(arr[newY][newX] == 0) {
                                near = true;
                                cpArr[newY][newX] = 3;
                                queue.add(new Point(newX, newY));
                            }
                            if(arr[newY][newX] == 2) {
                                queue.add(new Point(newX, newY));
                            }
                        }
                    }
                }
            }
            
            if(!near) {
                temp++;
            }else {
                result += ++temp;
                temp = 0;
            }
        }
        
        if(!isPossible(cpArr))
            return -1;
        
        
        return result;
    }
}