고양멍멍이

[문제링크]

* 요약하자면 y번째 자리에 x번 수가 있을때

  - y자릿수를 만드는데 필요한 index를 x번 가산 ( 1 ~ y-1 자리에 등장하는 수 처리 )

  - 앞에서 등장한 prev 숫자들을 x*y번 가산 ( y+1 ~ 자리에 등장하는 수 처리 )

  - x보다 작은 수들을 y자릿수씩 가산 ( y 자리에 등장하는 수 처리 )

  - 3부분으로 나눠 처리하는 방법이다

0. 10단위로, 그 아랫 페이지까지 나오는 0~9의 갯수를 미리 계산해 저장한다

  - 1000페이지 미만까지 나오는 숫자는, 100페이지 미만에서 나오는 숫자들이 10회 반복해서 나오고

    + 1~9(앞자리)가 각 100번씩 나온다

  - 계산의 편의를 위해 0 또한 앞자리로 존재한다고 가정하고 연산, 마지막에 제거한다

1. 앞에서부터 숫자와 자릿수를 추출한다 ( cur, len )

2. len에 해당하는 index의 값을, cur번 더해준다 ( 

  - ex) 543에서 5를 처리할 때 : 5와 3(100의 자릿수)을 추출, index의 3번째(100까지 나오는 숫자) 배열을 5회 가산

3. prev배열은 앞에서 등장한 숫자 정보를 가지고 있으며, 현재 자리에서 반복하는 횟수만큼 가산된다

  - ex) 543에서 4를 처리할 때 : 5는 40회 가산되어야한다

4. 현재 cur에 대해, 0~cur-1까지의 숫자는 자릿수만큼 등장하므로, 가산해준다

  - ex) 543에서 4를 처리할 때, 0,1,2,3은 10번씩 등장할 것이다

5. 마지막 자리를 처리할때는, prev배열을 1회 추가로 가산해야 한다

  - 543에서 4를 처리할 때는 prev배열을 50X, 51X, 52X, 53X에 대해 4 * 10회 가산해주고,

  - 54X에 대한 처리는 X가 불확실하므로 아래 자릿수에서 하게 된다

  - 하지만 마지막 자릿수인 3에선 불확실한 수가 없으므로 540, 541, 542, 543 총 4 * 1회 해주게 된다

6. 맨 앞에 등장한 0을 제거한다.

  - 가장 앞의 0은 1의 자릿수에선 1번, 10의 자릿수에선 10번, 100의 자릿수에선 100번 등장한다.

  - ex) 543은 100의 자릿수이므로, 총 111번의 0이 등장한다

  - 주어진 수의 자릿수까지 1, 10, 100을 계속 빼준다

7. 나중에 다시 보기위해 작성한 설명인데, 미래의 내가 이걸 알아들을지 자신이 없다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long[]page = new long[10];
		long[]prev = new long[10];
		long[]ans = new long[10];
		
		ArrayList<long[]>index=new ArrayList<>();
		index.add(page.clone());
		int cnt=1;
		//전처리
		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				page[j]*=10;
				page[j]+=cnt;
			}
			index.add(page.clone());
			cnt*=10;
		}

		String N = br.readLine();
		int len = N.length();
		
		//0번 자리부터
		for (int i = 0; i < N.length(); i++, len--) {
			int cur = N.charAt(i)-'0';

			long[] curIdx = index.get(len-1);
			long repeat = (long)Math.pow(10, len-1);
			for (int j = 0; j <= 9; j++) {
				ans[j]+=curIdx[j]*cur;
				ans[j]+=prev[j]*repeat*cur;//prev처리
			}
			
			//가장 앞자리 처리
			for (int j = 0; j < cur; j++) {
				ans[j]+=repeat;
			}
			
			prev[cur]++;
		}
		for (int j = 0; j <= 9; j++) ans[j]+=prev[j]; // prev배열 추가 1회 처리
		for (int i = 0; i < N.length(); i++) ans[0]-=Math.pow(10, i); // 맨 앞에 등장한 0 처리
		for (int i = 0; i <= 9; i++) System.out.print(ans[i]+" ");
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 블록의 길이는 n*m이며 블록 중간에는 상점도 길도 없으므로 한바퀴 도는 경로를 n+m+n+m크기의 1차원 배열로 관리할 수 있다

1. 북쪽 > 동쪽 > 남쪽 > 서쪽 순서의 경로를 가정하고, 입력받은 상점의 위치를 가공해 저장한다

2. 마지막에 시작점을 입력받고, 배열을 한바퀴 순회(배열의 범위를 넘어가면 0으로 초기화)하며 거리를 누적한다

  - 거리는 정방향(i)과 역방향(totalLen - i) 중 짧은쪽을 누적한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		int[] map = new int[(n+m)*2];
		int store = pint(br.readLine());
		int pos=0;
		int totalCost=0; //최소 코스트 
		int totalLen = (n+m)*2; // 상점가 블록 전체의 갯수
		
		for (int i = 0; i <= store; i++) {
			int temp=0;
			st = new StringTokenizer(br.readLine());
			switch (st.nextToken()) {
			case "1"://북쪽
				temp=pint(st.nextToken());break;
			case "2"://남쪽
				temp=n+m+n-pint(st.nextToken());break;
			case "3"://서쪽
				temp=(n+m)*2-pint(st.nextToken());break;
			case "4"://동쪽
				temp=n+pint(st.nextToken());break;
			default: break;
			}
			if(i==store)pos=temp; // 마지막 입력은 시작 위치
			map[temp]=1;
		}
		for (int i = 1; i < totalLen; i++) {
			if(pos+i==totalLen)pos=-i;
			if(map[pos+i]==1) {
				totalCost+=Math.min(i, totalLen-i);
			}
		}System.out.println(totalCost);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 집에 n개의 공유기를 설치할 때, 가능한 최대 거리를 구하는 문제

  - 집 사이의 간격에 대해 바이너리서치 진행

1. 바이너리 서치의 시작점은 0, 끝점은 가장 먼 집의 좌표

2. 구한 dis에 따라, 최대한 그리디하게 집에 공유기를 설치했을 때의 갯수를 센다

3-1. 공유기가 목표 갯수를 충족했다면, ans를 갱신 후 min값을 갱신, 더 큰 dis를 시도해본다

3-1. 공유기가 목표 갯수에 미달했다면, max값을 갱신, 더 작은 dis를 시도해본다

4. min과 max가 교차하면 종료, 구한 ans값을 출력한다 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[]house = new int[n];
		for (int i = 0; i < n; i++) {
			house[i]=pint(br.readLine());
		}
		Arrays.sort(house);
		
		int min=0, max=house[n-1];
		int ans=0;
		while(min<=max) {
			int dis = (max+min)/2;
			
			int prev_house = house[0];
			int cnt=1;
			for (int i = 0; i < n; i++) {
				if(prev_house + dis <= house[i]) {
					prev_house=house[i];
					cnt++;
				}
			}
			if(cnt>=m) {
				ans=dis;
				min=dis+1;
				
			}else {
				max=dis-1;
			}
		}
		System.out.println(ans);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. reverseRow : 행을 뒤집고, rowSum/colSum을 갱신하는 함수

  - reverseCol : 열을 뒤집고, rowSum/colSum을 갱신하는 함수

  - toOrigin : 뒤집었던 열(t2변수에 bitmask로 저장됨)들을 복구하는 함수 

  - findmin : 부분집합을 만들고, 열을 뒤집고, 행을 검사하는 함수

1. 배열의 모든 행에 대해, 모든 가능한 부분집합을 만들어 reverse한다

2. 1번의 모든 경우에 대해, 값이 음수인 모든 열을 뒤집어본다

  - 값이 0인 열이 있다면 뒤집어도 0이므로, 양수가 될수 없으니 즉시 원상복귀 후 return한다

3. 2번을 통해 모든 열이 양수가 된 후에도 모든 행이 양수를 유지하고 있다면, 옳은 P배열이다

  - min값 갱신

4. min의 최댓값은 (N+M)/2이므로, (N+M)/2+1을 초깃값으로 정한다

  - ( N, M은 18 이하이므로 19 이상의 임의의 수를 사용해도 문제 없다 )

  - 동일한 값을 유지한다면 P배열을 만드는게 불가능했단 의미로, -1을 출력한다

  - 만드는게 가능했다면 구한 min값을 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	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());
		map=new int[N][M];
		rowSum = new int[N];
		colSum = new int[M];
		min=(N+M)/2+1;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				colSum[j]+=map[i][j];
				rowSum[i]+=map[i][j];
			}
		}
		findmin(0, 0);
		
		if(min==(N+M)/2+1)System.out.println(-1);
		else System.out.println(min);
		
	}
	static int[] rowSum;//행 합계
	static int[] colSum;//열 합계
	static int[][]map;
	static int N,M,min;
	
	static void findmin(int cnt, int colChk) {
		if(cnt==M) {
			//행을 뒤집은 부분집합 완성
			int temp=0, temp2=0;
			for (int i = 0; i < N; i++) {
				if(rowSum[i]==0) {
					toOrigin(temp2);
					return;
				}
				else if(rowSum[i]<0) {
					reverserow(i);
					temp++;
					temp2 = temp2|1<<i;
				}
			}
			for (int i = 0; i < M; i++) {
				if(colSum[i]<=0) {
					toOrigin(temp2);
					return;
				}
			}
			min=min<colChk+temp?min:colChk+temp;
			toOrigin(temp2);
			
			return;
		}
		
		//안선택
		findmin(cnt+1,colChk);
		//선택
		reversecol(cnt);
		findmin(cnt+1,colChk+1);
		reversecol(cnt);
		
		
	}
	static void toOrigin(int t2) {
		for (int i = 0; i < N; i++)if((t2&1<<i)!=0)reverserow(i);
	}
	
	static void reverserow(int idx) {
		for (int i = 0; i < M; i++) {
			map[idx][i] =-map[idx][i];
			colSum[i] = colSum[i] +map[idx][i]*2; 
		}
		rowSum[idx]*=-1;
	}
	static void reversecol(int idx) {
		for (int i = 0; i < N; i++) {
			map[i][idx]=-map[i][idx];
			rowSum[i] = rowSum[i] +map[i][idx]*2; 
		}
		colSum[idx]*=-1;
	}
	
	
}

[문제링크]

[문제링크]

0. 활주로 건설이 불가능한 경우는 2가지이다

  - 2칸 이상 차이가 나는 경우

  - 1칸 차이가 나지만 X칸만큼의 공간이 존재하지 않을 경우

1. 2칸 이상 차이가 난다면 불가능 처리한다

2. 높이가 동일한 경우, cnt로 갯수를 세가며 진행한다

  - 올라가야하는 상황이 생겼을 때, cnt가 X보다 크거나 같아야만 진행 가능하다

  - 올라간 칸에서부터 시작하므로 cnt값을 1로 초기화

3. 내려가야하는 상황이 생겼다면 앞에 X칸의 공간이 동일한 높이로 존재해야 진행 가능하다

  - 반목문으로 X칸의 높이를 확인, 다르면 불가능 처리한다

  - 전부 같다면, 현재 위치가 j였을때 j+X칸에서부터 다시 시작하므로, j+X-1으로 포인터를 옮긴다

  - 이때, j+X-1칸은 경사로의 마지막 칸이므로, cnt는 0으로 초기화

4. 위 과정을 모든 행/열에 대해 실행해주고 가능한 경우를 카운트

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int x = pint(st.nextToken());
			int[][]map = new int[n][n];

			for (int i = 0; i < n; i++) {
				st=new StringTokenizer(br.readLine()," ");
				for (int j = 0; j < n; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			
			int possibleCnt=0;
			
			for (int i = 0; i < n; i++) {
				//i번째 Row의 불가능 가능 여부를 탐색
				boolean isP = true;
				
				//1. 2칸 이상 차이나면 불가
				for (int j = 1; j < n; j++) {
					if(Math.abs(map[i][j] - map[i][j-1]) >=2)isP=false;
				}if(!isP)continue;
				
				//2. 1칸 올라|내려 가야하는데, 뒤|앞에 공간이 x칸 없으면 불가
				int prev=map[i][0];
				int cnt=1;
				for (int j = 1; j < n; j++) {
					//같으면 +
					if(prev == map[i][j])cnt++;
					else if(prev< map[i][j]) {
						//올라갈 때
						if(cnt>=x) {
							//ok
						}
						else {
							isP=false;
						}
						prev=map[i][j];
						cnt=1;//cnt초기화
					}
					else {
						//내려갈 때
						//앞에 x칸이 다 같은 높이로 존재하는지 확인
						//만족한다면, x 앞칸으로 포인터(j)이동
						prev = map[i][j];
						cnt=1;
						for (int j2 = 1; j2 < x; j2++) {
							if(j+j2 >= n)break;
							if(prev==map[i][j+j2])cnt++;
						}
						if(cnt!=x)isP=false;
						j = j+x-1;
						cnt=0;//cnt초기화
					}
				}
				if(isP)possibleCnt++;
			}
			
			for (int i = 0; i < n; i++) {
				//i번째 Col의 불가능 가능 여부를 탐색
				boolean isP = true;
				
				//1. 2칸 이상 차이나면 불가
				for (int j = 1; j < n; j++) {
					if(Math.abs(map[j][i] - map[j-1][i]) >=2)isP=false;
				}if(!isP)continue;
				
				//2. 1칸 올라|내려 가야하는데, 뒤|앞에 공간이 x칸 없으면 불가
				int prev=map[0][i];
				int cnt=1;
				for (int j = 1; j < n; j++) {
					//같으면 +
					if(prev == map[j][i])cnt++;
					else if(prev< map[j][i]) {
						//올라갈때
						if(cnt>=x) {
							//ok
						}
						else {
							isP=false;
						}
						prev=map[j][i];
						cnt=1;//cnt초기화
					}
					else {
						//내려갈 때
						//앞에 x칸이 다 같은 높이로 존재하는지 확인
						//만족한다면, x 앞칸으로 포인터(j)이동
						prev = map[j][i];
						cnt=1;
						for (int j2 = 1; j2 < x; j2++) {
							if(j+j2 >= n)break;
							if(prev==map[j+j2][i])cnt++;
						}
						if(cnt!=x)isP=false;
						j = j+x-1;
						cnt=0;
					}
					
				}
				if(isP)possibleCnt++;
			}
			
			sb.append("#").append(testcase).append(" ").append(possibleCnt).append("\n");
		}
		System.out.println(sb);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 모든 가방 무게에 대해, n-1번째 물건을 고려한 최적의 선택이 존재한다고 하면,

n번째 물건의 무게가 w, 가치가 v일때 무게 j짜리 가방의 최적해는

  - n번째 물건을 선택하지 않는 경우 ( n-1번의 무게 j짜리 최적해 )

  - n번째 물건을 선택한 경우 ( v + n-1번의 무게 j-w짜리 최적해 )

둘 중 큰 경우이다

1. 가상의 무게 0, 가치 0인 물건을 가정한다. ( 첫번째 연산에서 '이전 결과값'의 역할을 한다)

2. 첫번째 물건부터 차례대로, 가능한 모든 무게에 대해 넣는 경우와 넣지 않는 경우를 비교해 둘 중 큰 값을 선택한다

3. n번째 물건까지 종료한 최종 값이 최적해가 된다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[][]item = new int[n][2];
		for (int i = 0; i < n; i++) {
			st=new StringTokenizer(br.readLine()," ");
			item[i][0]=pint(st.nextToken());
			item[i][1]=pint(st.nextToken());
		}
        //첫번째 행 / 열의 0 값은 dp 연산에서 사용한다
        int[][]dp = new int[n+1][m+1];
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(j>=item[i-1][0]) {
                	//넣을 수 있다면 넣는 경우와 안넣는 경우를 비교한다
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-item[i-1][0]]+ item[i-1][1]);
				}
				else {
                	//넣지 못한다면 이전 결과 유지
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		
		System.out.println(dp[n][m]);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 1번 노드에서 v1,v2를 거쳐 N번 노드로 이동하는 방법은 2가지이다

  - v1을 먼저 방문 : 1-v1-v2-N

  - v2를 먼저 방문 : 1-v2-v1-N

  - 조건상 두 지점간 거리의 최댓값은 800개의 노드 가 1000 길이의 길로 연결됬을 경우인 799K이다

1. 1번노드, v1번 노드, v2번 노드에서 각각 다익스트라를 돌려, 다른 노드로 가는 최솟값을 찾는다

2. 다익스트라 계산 후 1-v1-v2-N 과 1-v2-v1-N 두 방법 중 cost가 작은것을 찾는다

3. 이론상 최대치가 약 80만이므로, 1-v1 / v1-v2 / v2-N 3번의 이동이 다 최대 cost에 가깝다고 해도 총 cost는 240만보다 작다

  - cost가 300만 이상의 결과가 나왔다면 경로가 존재하지 않아 초깃값이 계산된 경우이므로 -1을 출력한다

  - 그 외라면 구한 cost를 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());

		int[][]graph = new int[n+1][n+1];
		
		for (int i = 0; i < m; i++) {
			st=new StringTokenizer(br.readLine()," ");
			int n1 = pint(st.nextToken());
			int n2 = pint(st.nextToken());
			int c = pint(st.nextToken());
			graph[n1][n2]=c;
			graph[n2][n1]=c;
		}
		st=new StringTokenizer(br.readLine()," ");
		int n1 = pint(st.nextToken());
		int n2 = pint(st.nextToken());
	
		//다익스트라 준비물 * 3
		int[]dilk1=new int[n+1];
		int[]dilkn1=new int[n+1];
		int[]dilkn2=new int[n+1];
		Arrays.fill(dilk1, 3000000);
		Arrays.fill(dilkn1, 3000000);
		Arrays.fill(dilkn2, 3000000);
		
		boolean[] isV=new boolean[n+1];
		boolean[] isVn1=new boolean[n+1];
		boolean[] isVn2=new boolean[n+1];
		dilk1[1]=0;
		dilkn1[n1]=0;
		dilkn2[n2]=0;
		
		for (int i = 0; i < n; i++) {
			//아직 방문 안한 노드 중 가장 가까운 노드 탐색
			int min=Integer.MAX_VALUE, minnode=0;
			int minn1=Integer.MAX_VALUE, minnoden1=0;
			int minn2=Integer.MAX_VALUE, minnoden2=0;
			for (int j = 1; j <= n; j++) {
				if(!isV[j] && dilk1[j]<min) {
					min=dilk1[j];
					minnode=j;
				}if(!isVn1[j] && dilkn1[j]<minn1) {
					minn1=dilkn1[j];
					minnoden1=j;
				}if(!isVn2[j] && dilkn2[j]<minn2) {
					minn2=dilkn2[j];
					minnoden2=j;
				}
			}
			//해당 노드 방문처리
			isV[minnode]=true;
			isVn1[minnoden1]=true;
			isVn2[minnoden2]=true;
			
			for (int j = 1; j <= n; j++) {
				//아직 방문 안한 노드에 대해 cost 업데이트
				if(!isV[j] && graph[minnode][j]!=0) {
					dilk1[j]=Math.min(dilk1[j], dilk1[minnode]+graph[minnode][j]);
				}
				if(!isVn1[j] && graph[minnoden1][j]!=0) {
					dilkn1[j]=Math.min(dilkn1[j], dilkn1[minnoden1]+graph[minnoden1][j]);
				}
				if(!isVn2[j] && graph[minnoden2][j]!=0) {
					dilkn2[j]=Math.min(dilkn2[j], dilkn2[minnoden2]+graph[minnoden2][j]);
				}
			}
			
		}
		
		//1->n1->n2->n
		int cost=3000000;
		
		cost = Math.min(dilk1[n1]+dilkn1[n2]+dilkn2[n], dilk1[n2]+dilkn2[n1]+dilkn1[n]);
		if(cost>=3000000)System.out.println(-1);
		else System.out.println(cost);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 모든 경우의 수를 탐색 - BFS

  - 같은 공간 큰 cost를 가지고 접근할 경우 더이상 진행하지 않으므로, DFS보다 수행횟수가 적다

  - 외각을 -1로 감싸 나가지 못하도록 처리

1. (1, 1) 좌표부터 bfs 진행 후 N,N좌표의 cost가 최소 cost

개선점

1. 현재 bfs는 2-3-4순으로 진입시 3,4에 대해선 진행하지 않지만, 4-3-2순으로 진입시 4,3,2 전부 실행하게된다.

  - priority queue를 이용해 해결 가능

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution{
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			int N = pint(br.readLine());
			int[][] map = new int[N+2][N+2];
			int[][] cost = new int[N+2][N+2];
			
			//외곽설정, cost초기화
			for (int i = 0; i < N+2; i++) {
				map[0][i]=-1;map[N+1][i]=-1;
				map[i][0]=-1;map[i][N+1]=-1;
				Arrays.fill(cost[i], Integer.MAX_VALUE);
			}
			
			//입력받기
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i+1][j+1]=s.charAt(j)-'0';
				}
			}
			
			Queue<int[]> qu = new LinkedList<>();
			qu.offer(new int[] {1,1});
			cost[1][1]=0;
			
			while(!qu.isEmpty()) {
				int[]cur = qu.poll();
				int curCost = cost[cur[0]][cur[1]];
				
				//더 작은 코스트로 진행할 수 있다면
				for (int i = 0; i < 4; i++) {
					int tx=cur[0]+dx[i], ty=cur[1]+dy[i];
					
					if(map[ tx ][ ty ]!=-1 && curCost + map[ tx ][ ty ] < cost[ tx ][ ty ]) {
						qu.offer(new int[] {tx, ty});
						cost[ tx ][ ty ]=curCost+map[ tx ][ ty ];
					}
				}
			}
			sb.append("#").append(testcase).append(" ").append(cost[N][N]).append("\n");
		}
		System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}