結果
| 問題 | No.323 yuki国 |
| ユーザー |
 Grenache
|
| 提出日時 | 2015-12-17 00:14:39 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,208 bytes |
| コンパイル時間 | 5,414 ms |
| コンパイル使用メモリ | 80,496 KB |
| 実行使用メモリ | 37,852 KB |
| 最終ジャッジ日時 | 2024-09-16 06:34:09 |
| 合計ジャッジ時間 | 7,008 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 29 WA * 3 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintStream;import java.io.PrintWriter;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.Iterator;public class Main_yukicoder323 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Printer pr = new Printer(System.out);int h = sc.nextInt();int w = sc.nextInt();int a = sc.nextInt();int si = sc.nextInt();int sj = sc.nextInt();int b = sc.nextInt();int gi = sc.nextInt();int gj = sc.nextInt();char[][] akichi = new char[h][];for (int i = 0; i < h; i++) {akichi[i] = sc.next().toCharArray();}if (Math.abs(a - b) % 2 != Math.abs(si - gi + sj - gj) % 2) {pr.println("No");sc.close();pr.close();return;}int[] di = {-1, 0, 1, 0};int[] dj = {0, 1, 0, -1};boolean flag1 = false;boolean flag2 = false;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {for (int k = 0; k < 2; k++) {int ni = i + di[k];int nj = j + dj[k];if (ni < 0 || nj >= w) {continue;}if (akichi[i][j] == akichi[ni][nj]) {if (akichi[i][j] == '*') {flag1 = true;} else {flag2 = true;}}}}}int g = 0;for (int k = 0; k < di.length; k++) {int ni = gi + di[k];int nj = gj + dj[k];if (ni < 0 || ni >= h || nj < 0 || nj >= w) {continue;}g++;}if (g == 1 && akichi[gi][gj] == '*' && b == 1) {pr.println("No");sc.close();pr.close();return;}boolean ret = false;if (flag1 && flag2) {ret = isOk(akichi, di, dj, a, si, sj, b, gi, gj);} else if (flag1) {int[][] yuki = getYuki(akichi, di, dj, a, si, sj, b, gi, gj, true);if (yuki[gi][gj] <= b && yuki[gi][gj] > 0) {ret = true;}} else if (flag2) {int[][] yuki = getYuki(akichi, di, dj, a, si, sj, b, gi, gj, false);if (yuki[gi][gj] >= b) {ret = true;}} else {int[][] yuki = getYuki(akichi, di, dj, a, si, sj, b, gi, gj, true);if (yuki[gi][gj] == b) {ret = true;}}if (ret) {pr.println("Yes");} else {pr.println("No");}pr.close();sc.close();}private static int[][] getYuki(char[][] akichi, int[] di, int[] dj, int a, int si, int sj, int b, int gi, int gj, boolean min) {int h = akichi.length;int w = akichi[0].length;int[][] yuki = new int[h][w];if (min) {for (int i = 0; i < h; i++) {Arrays.fill(yuki[i], Integer.MAX_VALUE);}}Deque<Integer> qi = new ArrayDeque<Integer>();Deque<Integer> qj = new ArrayDeque<Integer>();qi.add(si);qj.add(sj);yuki[si][sj] = a;while (!qi.isEmpty()) {int i = qi.remove();int j = qj.remove();for (int k = 0; k < di.length; k++) {int ni = i + di[k];int nj = j + dj[k];if (ni < 0 || ni >= h || nj < 0 || nj >= w) {continue;}int nyuki;if (akichi[ni][nj] == '*') {nyuki = yuki[i][j] + 1;} else {nyuki = yuki[i][j] - 1;}if (nyuki == 0) {continue;}if (min && yuki[ni][nj] > nyuki) {yuki[ni][nj] = nyuki;qi.add(ni);qj.add(nj);} else if (!min && yuki[ni][nj] < nyuki) {yuki[ni][nj] = nyuki;qi.add(ni);qj.add(nj);}}}return yuki;}private static boolean isOk(char[][] akichi, int[] di, int[] dj, int a, int si, int sj, int b, int gi, int gj) {int h = akichi.length;int w = akichi[0].length;int[][] yuki = new int[h][w];Deque<Integer> qi = new ArrayDeque<Integer>();Deque<Integer> qj = new ArrayDeque<Integer>();qi.add(si);qj.add(sj);yuki[si][sj] = a;while (!qi.isEmpty()) {int i = qi.remove();int j = qj.remove();for (int k = 0; k < di.length; k++) {int ni = i + di[k];int nj = j + dj[k];if (ni < 0 || ni >= h || nj < 0 || nj >= w) {continue;}if (akichi[i][j] == '*' && akichi[ni][nj] == '*') {return true;}int nyuki;if (akichi[ni][nj] == '*') {nyuki = yuki[i][j] + 1;} else {nyuki = yuki[i][j] - 1;}if (nyuki == 0) {continue;}if (yuki[ni][nj] >= nyuki) {continue;}yuki[ni][nj] = nyuki;qi.add(ni);qj.add(nj);}}if (yuki[gi][gj] >= b) {return true;}return false;}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Iterator<String> it;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext()) {it = Arrays.asList(br.readLine().split(" ")).iterator();}return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}float nextFloat() throws RuntimeException {return Float.parseFloat(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {// throw new IllegalStateException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}