結果
| 問題 | No.340 雪の足跡 |
| ユーザー |
 Grenache
|
| 提出日時 | 2016-06-19 15:54:50 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 4,193 bytes |
| コンパイル時間 | 3,810 ms |
| コンパイル使用メモリ | 79,716 KB |
| 実行使用メモリ | 70,460 KB |
| 最終ジャッジ日時 | 2024-10-11 05:22:10 |
| 合計ジャッジ時間 | 20,367 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 30 TLE * 2 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder340_1 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Printer pr = new Printer(System.out);int w = sc.nextInt();int h = sc.nextInt();int n = sc.nextInt();// ====================================// long stime = System.currentTimeMillis();// ====================================int[][] iw = new int[h][w];int[][] ih = new int[h][w];for (int i = 0; i < n; i++) {int m = sc.nextInt();int prev = 0;for (int j = 0; j < m + 1; j++) {int b = sc.nextInt();if (j > 0) {int ph = prev / w;int pw = prev % w;int nh = b / w;int nw = b % w;if (ph == nh) {iw[ph][Math.min(pw, nw)]++;iw[ph][Math.max(pw, nw)]--;} else if (pw == nw) {ih[Math.min(ph, nh)][pw]++;ih[Math.max(ph, nh)][pw]--;} else {}}prev = b;}}// ====================================// long etime = System.currentTimeMillis();// System.out.printf("time : %d\n", etime - stime);// ====================================for (int i = 0; i < h; i++) {for (int j = 0; j < w - 1; j++) {if (j > 0) {iw[i][j] += iw[i][j - 1];}}}for (int j = 0; j < w; j++) {for (int i = 0; i < h - 1; i++) {if (i > 0) {ih[i][j] += ih[i - 1][j];}}}// ====================================// etime = System.currentTimeMillis();// System.out.printf("time : %d\n", etime - stime);// ====================================int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};Queue<Integer> qx = new ArrayDeque<>();Queue<Integer> qy = new ArrayDeque<>();Queue<Integer> qd = new ArrayDeque<>();boolean[][] used = new boolean[h][w];qx.add(0);qy.add(0);qd.add(0);used[0][0] = true;while (!qx.isEmpty()) {int x = qx.remove();int y = qy.remove();int d = qd.remove();if (x == w - 1 && y == h - 1) {pr.println(d);// ====================================// etime = System.currentTimeMillis();// System.out.printf("time : %d\n", etime - stime);// ====================================pr.close();sc.close();return;}for (int i = 0; i < dx.length; i++) {int nx = x + dx[i];int ny = y + dy[i];if (nx < 0 || nx >= w || ny < 0 || ny >= h) {continue;}if (used[ny][nx]) {continue;}if (!isOK(x, y, nx, ny, ih, iw)) {continue;}qx.add(nx);qy.add(ny);qd.add(d + 1);used[ny][nx] = true;}}pr.println("Odekakedekinai..");// ====================================// etime = System.currentTimeMillis();// System.out.printf("time : %d\n", etime - stime);// ====================================pr.close();sc.close();}private static boolean isOK(int x, int y, int nx, int ny, int[][] ih, int[][] iw) {if (x == nx) {if (ih[Math.min(y, ny)][x] > 0) {return true;}} else if (y == ny) {if (iw[y][Math.min(x, nx)] > 0) {return true;}} else {}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);}}}