고양멍멍이

[문제링크]

0. 한번의 클릭으로 하나 이상의 칸을 처리할 수 있는건 0인 칸 뿐이다

1. 미리 지뢰가 아닌 칸의 개수를 세둔다 (cnt)

2. 주변 지뢰의 갯수로 정답 배열을 미리 만들어놓고, 0이면서 처리되지 않은 칸에 대해서만 재귀로 주변 처리

  - 한 칸 처리할때마다 cnt에서 1씩 뺀다

3. 모든 0에 대해 처리하고 나면, 나머지 칸들은 하나하나 직접 눌러줘야한다 (남은 cnt만큼)

4. 0을 누른 횟수 + 나머지를 누른 횟수 = 정답

import java.io.BufferedReader;
import java.io.InputStreamReader;

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++) {
			N = pint(br.readLine());
			map = new int[N][N];
			ansMap = new int[N][N];
			
			int pressCnt=0;//몇번 눌러야 하는가?
			cnt=0;//지뢰가 아닌 땅 cnt
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j]=s.charAt(j);
					if(map[i][j]=='.')cnt++;
				}
			}
			//정답배열 생성
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					for (int x = Math.max(i-1, 0); x < Math.min(i+2, N) ; x++) {
						for (int y = Math.max(j-1, 0); y < Math.min(j+2, N); y++) {
							if(map[x][y]=='*')ansMap[i][j]++;
						}
					}
				}
			}
			
			//모든 0부터 눌러본다
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(ansMap[i][j]==0 && map[i][j]=='.') {
						press(i,j);
						pressCnt++;
					}
				}
			}

			sb.append("#").append(testcase).append(" ").append(pressCnt+cnt).append("\n");
			
		}System.out.println(sb);
	}
    
	static int cnt,N;
	static int[][]map;
	static int[][]ansMap;
	static int[]dx = {1,1,0,-1,-1, -1, 0, 1};
	static int[]dy = {0,1,1, 1, 0, -1,-1,-1};
    
	static void press(int x, int y) {
		if(ansMap[x][y]!=0) {
			cnt--;
			map[x][y]=ansMap[x][y];
		}
		else {
			cnt--;
			map[x][y]=0;
			for (int i = 0; i < 8; i++) {
				int tx = x+dx[i], ty=y+dy[i];
				if(tx<0||tx>=N||ty<0||ty>=N||map[tx][ty]!='.')continue;
				press(x+dx[i],y+dy[i]);
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. x,y지점에서 총 m칸, 최대 무게 c를 고려해 채취할 수 있는 꿀의 최대 가치는 항상 동일하다

  - 미리 연산해서 저장 후 활용한다

1. 위에서 구한 가치들 중, 구간이 겹치지 않으면서 가치의 합이 최대가 되는 두 구역을 찾는다

2. 가치가 큰 순서로 정렬한다

  - 최대 가치 구간을 한 구간으로 잡고 그리디하게 계산한 최댓값이 최댓값이 아니려면

  - 최대 가치 구간과 영역이 겹치는 다른 구간에서 나온 값만이 가능하다

3. 영역이 겹치는 구간의 수는 2*m-1개로, 정렬된 구간을 그만큼만 살펴보면

  - 그리디하게 구한 결과의 가능한 모든 반례를 고려한 결과가 나온다

* 최대 가치를 가지는 영역 X와, 이에 속하지 않는 영역중 최대 가치를 가진 Y의 합 : 그리디한 해결법 으로 생각하면

  - X+Y의 가치보다 큰 값은 X와 영역이 일부 겹치는 X'들이 서로 합쳐졌을때만 가능하다

  - m이 3이라면, n이 충분할 때 겹치는 영역은 최대 5개(자기 자신 포함) 

  - 1위가 최대영역 X이고, 2,3,4,5위가 X와 영역을 공유할 때 그리디한 답은 1위 + 6위

  - 2,3,4,5위의 해답만이 1+6위의 결과를 넘을 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
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(), " ");
			n = pint(st.nextToken());
			m = pint(st.nextToken());
			c = pint(st.nextToken());
			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());
				}
			}
			collect = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n-m+1; j++) {
					int temp =calMax(i,j,0,0,0); 
					collect.add(new int[] {i, j, temp});
				}
			}
			
			Collections.sort(collect, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[2]-o1[2];
				}
			});
			
			int max=0, len = Math.min(m*2-1, n-m+1);
			for (int i = 0; i < len; i++) {
				int[] fst = collect.get(i);
				for (int j = i+1; j < collect.size(); j++) {
					int[] snd = collect.get(j);
					if(fst[0]==snd[0] && Math.abs(fst[1]-snd[1])<m)continue;
					
					if(max<fst[2]+snd[2]) {
						max=fst[2]+snd[2]; break;
					}
				}
			}
			sb.append("#").append(testcase).append(" ").append(max).append("\n");
		}System.out.println(sb);
	}
    
	static int n,m,c;
	static int[][]map;
	static ArrayList<int[]>collect;
    
	static int calMax(int i,int j, int cost, int wid, int cnt) {
		if(wid>c)return 0;
		if(cnt==m) {
			return cost;
		}
		int temp=0;
		temp = calMax(i,j+1, cost+map[i][j]*map[i][j], wid + map[i][j], cnt+1);
		temp = Math.max(temp, calMax(i,j+1, cost, wid, cnt+1));
		return temp;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. state 클래스로 정보를 관리 (x좌표, y좌표, 이전이동, 이동횟수)

1. bfs처럼 진행하되, 항상 목표지점으로 다가가는 이동이 최적의 이동이다

  - 현재 좌표와 목표좌표를 비교, 나아가야 할 방향을 결정한다

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

public class Solution{
	
	static class state {
		public int x,y,prev,cost;
		public state(int x, int y, int prev, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.prev = prev;
			this.cost = cost;
		}
	}
	
	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 sx = pint(st.nextToken());
			int sy = pint(st.nextToken());
			int dx = pint(st.nextToken());
			int dy = pint(st.nextToken());
			
			Queue<state>qu=new LinkedList<>();
			
			if(sx==dx && sy==dy) {
				sb.append("#").append(testcase).append(" ").append(0).append("\n");
				continue;
			}
			
			if(sx<dx)qu.offer(new state(sx+1,sy,1,1));
			else qu.offer(new state(sx-1,sy,1,1));
			if(sy<dy)qu.offer(new state(sx,sy+1,2,1));
			else qu.offer(new state(sx,sy-1,2,1));
			
			while(true) {
				state cur = qu.poll();
				System.out.println(cur.x+" "+cur.y);
				if(cur.x==dx && cur.y==dy) {
					sb.append("#").append(testcase).append(" ").append(cur.cost).append("\n");
					break;
				}
				
				if(cur.prev==2) {
					if(cur.x<dx)qu.offer(new state(cur.x+1, cur.y, 1, cur.cost+1));
					else qu.offer(new state(cur.x-1, cur.y, 1, cur.cost+1));
				}
				else {
					if(cur.y<dy)qu.offer(new state(cur.x, cur.y+1, 2, cur.cost+1));
					else qu.offer(new state(cur.x, cur.y-1, 2, cur.cost+1));
				}
				
			}
		}System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 가장 먼 점이 원점으로 이동할 때까지, 먼저 원점에 도달한 점들은 +1 -1 운동을 반복하게 된다

  - 모든 점들의 2로 나눈 나머지가 같지 않다면, 점들의 움직임이 일치하지 않아 한 점으로 모이는게 불가능하다

1. 입력받으며, 모든 수가 홀수 or 짝수로 통일되있는지 확인한다

  - 통일되있지 않으면, -1을 출력

2. 동시에, 입력값중 최댓값을 탐색한다

  - 모든 값이 홀/짝수로 통일되 있다면, 최댓값이 원점에 도달하는 순간 종료된다

3. 매 초 이동량의 누적값을 구하여 그 값이 max보다 크면서 max와의 차이가 짝수일 때 종료한다

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++) {
			int N = pint(br.readLine());
			int[] len = new int[N];
			int sum=0;
			int cnt=0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			len[0]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
			int max=len[0];
			for (int i = 1; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				len[i]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
				max=Math.max(max, len[i]);
				if(len[i]%2 != len[i-1]%2) {
					cnt=-1;
				}
			}
			
			if(cnt==0) {
				while(true) {
					boolean isE=true;
					if(sum<max || (max-sum)%2!=0) {
						isE=false;
					}
					if(isE)break;
					sum+=++cnt;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
			
		}System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 현재 파이프의 모양 - 인접 파이프의 모양 에 따라 갈수 있는지 없는지 여부가 결정된다

  - 총 4방향이므로, 4개의 bit에 bitmask로 저장해 정보를 나타낸다.

1. 입력값(0~7)에 따라 해당하는 bitmask정보를 부여한다

2. 시작점에서 time만큼 bfs를 돌며

  - 현재 노드에서 상/하/좌/우 통로가 존재하고 + 진행 노드에서 하/상/우/좌 통로가 존재한다면

  - 진행 가능, 큐에 넣는다

  - 방문체크 대신 큐에 넣을때 자기 위치의 값을 0으로 바꿔 재방문을 방지한다

3. time이 다 지났다면 (혹은 도중에 탐색을 마쳐 qu가 비었다면)

  - 방문할때마다 1씩 증가시켜준 cnt를 출력, 종료한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
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 m = pint(st.nextToken());
			int x = pint(st.nextToken())+1;
			int y = pint(st.nextToken())+1;
			int t = pint(st.nextToken());
			
			int[][] map = new int[n+2][m+2];
			
			for (int i = 1; i < n+1; i++) {
				st=new StringTokenizer(br.readLine()," ");
				for (int j = 1; j < m+1; j++) {
					int temp = pint(st.nextToken());
					if(temp==1)map[i][j]=0b1111;
					else if(temp==2)map[i][j]=0b1100;
					else if(temp==3)map[i][j]=0b0011;
					else if(temp==4)map[i][j]=0b1001;
					else if(temp==5)map[i][j]=0b0101;
					else if(temp==6)map[i][j]=0b0110;
					else if(temp==7)map[i][j]=0b1010;
				}
			}
			
			Queue<int[]> qu = new LinkedList<int[]>();
			qu.add(new int[] {x,y});
			int cnt=0;
			int time=0;
			while(time++<t && !qu.isEmpty()) {
				int len = qu.size();
				
				for (int i = 0; i < len; i++) {
					int[] cur=qu.poll();
					int temp = map[cur[0]][cur[1]];
					if(temp==0)continue;
					
					if((temp&1<<3)!=0 && (map[cur[0]-1][cur[1]]&1<<2)!=0)
						qu.offer(new int[] {cur[0]-1,cur[1]});
					if((temp&1<<2)!=0 && (map[cur[0]+1][cur[1]]&1<<3)!=0)
						qu.offer(new int[] {cur[0]+1,cur[1]});
					if((temp&1<<1)!=0 && (map[cur[0]][cur[1]-1]&1<<0)!=0)
						qu.offer(new int[] {cur[0],cur[1]-1});
					if((temp&1<<0)!=0 && (map[cur[0]][cur[1]+1]&1<<1)!=0)
						qu.offer(new int[] {cur[0],cur[1]+1});
					
					cnt++;
					map[cur[0]][cur[1]]=0;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
		}//end of tc
		System.out.println(sb);
	}

	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. shoot함수 : n번째 구슬을 모든 경우의 수에 대해 쏴보고, n+1번째로 재귀하는 함수

  - remove함수 : x, y좌표의 벽돌이 깨졌을 경우 모든 벽돌을 재귀로 깨는 함수

  - getDown함수 : 벽돌을 깬 후 모든 벽돌을 빈공간 없이 아래로 쌓는 함수

1. shoot함수가 모든 경우의 수에 대해 remove -> getDown 해본다

2. n번 구슬을 쐈을때 남아있는 ball값과 min을 비교, 갱신

* ball(remain)값을 인자로 넘기지 말고 전역변수로 관리할 수 있을것같은데, 피곤해서 포기

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

public class Solution{
	
	static int n,w,h,ball,min;
	static int[][]map;
	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++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = pint(st.nextToken());
			w = pint(st.nextToken());
			h = pint(st.nextToken());
			ball = 0;
			map = new int[h][w];
			
			for (int i = 0; i < h; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < w; j++) {
					map[i][j]=pint(st.nextToken());
					if(map[i][j]!=0)ball++;
				}
			}
			min=ball;
			shoot(0,ball);
			
			sb.append("#").append(testcase).append(" ").append(min).append("\n");
		}
		System.out.println(sb);
	}
	
	static void shoot(int cnt, int remain) {
		if(cnt==n) {
			min=Math.min(min, remain);
			return;
		}
		//현재 정보 백업
		int[][]backup = new int[h][w];
		for (int x = 0; x < h; x++) {
			for (int y = 0; y < w; y++) {
				backup[x][y]=map[x][y];
			}
		}
		int ballBackup=ball;

		for (int i = 0; i < w; i++) {
			// 정보 원상복구
			for (int x = 0; x < h; x++) {
				for (int y = 0; y < w; y++) {
					map[x][y]=backup[x][y];
				}
			}
			ball=ballBackup;

			for (int j = 0; j < h; j++) {
				if(map[j][i]!=0) {
					remove(j,i); // 제거하고
					getDown(); // 아래로 정렬하고
					break;
				}
			}
			shoot(cnt+1, ball); // 다음 발사로 재귀
			
		}
	}
	
	static void remove(int x, int y) {
		int c = map[x][y];
		map[x][y]=0;
		--ball;
		for (int j = 0; j < 4; j++) {
			int tx=x, ty=y;
			for (int i = 1; i < c; i++) {
				tx += dx[j];
				ty += dy[j];
				if(tx<0 || tx>=h || ty<0 || ty>=w)break;
				if(map[tx][ty]!=0)remove(tx,ty);
			}
		}
	}
	
	static void getDown() {
		for (int i = 0; i < w; i++) {
			int cnt=h-1;
			for (int j = h-1; j >=0 ; j--) {
				if(map[j][i]!=0) {
					int t = map[j][i];
					map[j][i]=0;
					map[cnt--][i]=t;
				}
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

[문제링크]

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. 모든 경우의 수를 탐색 - 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);
	}
}