import java.io.*; import java.util.*; public class Main { static int h,w; static int[][] s; static int[][] dp1; static int[][] dp2; static int[][] dp3; static boolean[][] visit; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for (int k = 0; k < t; k++) { StringTokenizer st = new StringTokenizer(br.readLine()); h = Integer.parseInt(st.nextToken()); w = Integer.parseInt(st.nextToken()); s=new int[h+2][w+2]; dp1=new int[h+2][w+2]; dp2=new int[h+2][w+2]; dp3=new int[h+2][w+2]; List start=new ArrayList<>(); for (int i = 0; i <= h+1; i++) { for (int j = 0; j <= w+1; j++) { dp1[i][j]=Integer.MAX_VALUE; dp2[i][j]=Integer.MAX_VALUE; dp3[i][j]=Integer.MAX_VALUE; } } for (int i = 1; i <= h; i++) { String input = br.readLine(); for (int j = 1; j <= w; j++) { if(input.charAt(j-1)=='*'){s[i][j]=-1;} else if(input.charAt(j-1)=='#'){s[i][j]=1;} else if(input.charAt(j-1)=='.'){s[i][j]=0;} else if(input.charAt(j-1)=='$'){start.add(new int[]{i,j});} } } start.add(new int[]{0,0}); bfs(start.get(0),dp1); bfs(start.get(1),dp2); bfs(start.get(2),dp3); int min=Integer.MAX_VALUE; for (int i = 0; i <= h+1; i++) { for (int j = 0; j <= w+1; j++) { if (dp1[i][j] != Integer.MAX_VALUE && dp2[i][j] != Integer.MAX_VALUE && dp3[i][j] != Integer.MAX_VALUE) { int x=dp1[i][j]+dp2[i][j]+dp3[i][j]; if(s[i][j]==1){x-=2;} min=Math.min(min,x); } } } sb.append(min + "\n"); } System.out.println(sb); } static int bfs(int[] start,int[][] dis){ Deque q=new ArrayDeque<>(); q.add(start); dis[start[0]][start[1]]=0; int[] dx = {1, -1, 0, 0}; int[] dy = {0, 0, 1, -1}; visit=new boolean[h+2][w+2]; while (!q.isEmpty()) { int[] temp=q.poll(); int ox=temp[1]; int oy=temp[0]; for (int i = 0; i < 4; i++) { int x = ox + dx[i]; int y = oy + dy[i]; if ((x >= 0 && y >= 0) && (x <= w+1 && y <= h+1) &&!visit[y][x]) { if (s[y][x] != -1) { if (dis[y][x] > dis[oy][ox]) { int cost=(s[y][x]==1)?1:0; cost+=dis[oy][ox]; if(s[y][x]==1){q.addFirst(new int[]{y,x});} else{q.addLast(new int[]{y,x});} dis[y][x]=cost; visit[y][x]=true; } } } } } return -1; } }

제출 #104362

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: