#nullable disable using System.Text; class Program { static void Main() { using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput())); using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput())); int testcase = int.Parse(sr.ReadLine()); for (int t = 0; t < testcase; t++) { string[] input = sr.ReadLine().Split(); int n = int.Parse(input[0]); int m = int.Parse(input[1]); char[,] board = new char[m,n]; (int x, int y) con1 = (-1, -1); (int x, int y) con2 = (-1, -1); int[,,] distance = new int[m, n, 3]; int[] dx = { -1, 1, 0, 0 }; int[] dy = { 0, 0, -1, 1 }; List<(int x, int y, int cost)> startPos = new List<(int, int, int)>(); for (int y = 0; y < n; y++) { string line = sr.ReadLine(); for (int x = 0; x < m; x++) { board[x, y] = line[x]; distance[x,y,0] = int.MaxValue; distance[x,y,1] = int.MaxValue; distance[x,y,2] = int.MaxValue; if (line[x] == '$') { board[x, y] = '.'; if(con1 == (-1,-1)) con1 = (x,y); else con2 = (x,y); } } } PriorityQueue<(int x, int y, int cost, int value), int> queue = new(); for (int x = 0; x < m; x++) { if (board[x,0] == '.') startPos.Add((x, 0, 0)); else if (board[x, 0] == '#') startPos.Add((x, 0, 1)); if (board[x,n-1] == '.') startPos.Add((x, n - 1, 0)); else if (board[x,n-1] == '#') startPos.Add((x, n - 1, 1)); } for (int y = 0; y < n; y++) { if (board[0, y] == '.') startPos.Add((0, y, 0)); else if (board[0, y] == '#') startPos.Add((0, y, 1)); if (board[m - 1, y] == '.') startPos.Add((m - 1, y, 0)); else if (board[m - 1, y] == '#') startPos.Add((m - 1, y, 1)); } foreach ((int x, int y, int cost) in startPos) { distance[x,y,0] = cost; queue.Enqueue((x, y, cost, 0), cost); } distance[con1.x, con1.y, 1] = 0; distance[con2.x, con2.y, 2] = 0; queue.Enqueue((con1.x, con1.y, 0, 1), 0); queue.Enqueue((con2.x, con2.y, 0, 2), 0); while (queue.Count > 0) { (int x, int y, int cost, int value) = queue.Dequeue(); if (cost > distance[x, y, value]) continue; for (int i = 0; i < 4; i++) { int px = x + dx[i]; int py = y + dy[i]; if(px < 0 || py < 0 || px >= m || py >= n) continue; if (board[px, py] == '*') continue; if (board[px, py] == '.') { if (cost < distance[px, py, value]) { distance[px,py,value] = cost; queue.Enqueue((px, py, cost, value), cost); } } if (board[px, py] == '#') { int curcost = cost + 1; if (curcost < distance[px, py, value]) { distance[px,py,value] = curcost; queue.Enqueue((px, py, curcost, value), curcost); } } } } int minValue = int.MaxValue; for (int y = 0; y < n; y++) { for (int x = 0; x < m; x++) { int value1 = distance[x, y, 0]; int value2 = distance[x, y, 1]; int value3 = distance[x, y, 2]; if (value1 == int.MaxValue || value2 == int.MaxValue || value3 == int.MaxValue) continue; int value = value1 + value2 + value3; if (board[x, y] == '#') value -= 2; minValue = Math.Min(minValue, value); } } sw.WriteLine(minValue); } } }

제출 #110975

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: