algorithms software expert

소프트웨어 익스퍼트 1249 (software expert 1249)

소프트웨어 익스퍼트 1249 (software expert 1249)

목차

소프트웨어 익스퍼트 1249

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class SWE1249 {
    final static int INF = Integer.MAX_VALUE;
    static int t, T, n, w;
    static int[] a = new int[1000001];
    static int[] d = new int[1000001];
    static boolean[] v = new boolean[1000001];
    static String in;
    static ArrayList<Edge>[] g = new ArrayList[1000001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        t = Integer.parseInt(br.readLine());T = t;
        for (int i = 0; i < 1000001; i++) {
            g[i] = new ArrayList<>();
        }
        while (T-- != 0) {
            n = Integer.parseInt(br.readLine());
            for (int i = 0; i < 1000001; i++) {
                g[i].clear();
            }
            Arrays.fill(a, 0);Arrays.fill(d, INF);
            for (int i = 0; i < n; i++) {
                in = br.readLine();
                for (int j = 0; j < n; j++) {
                    a[i * n + j] = in.charAt(j) - 48;
                }
            }
            int[] dx = {-1, 1, n, -n};
            for (int i = 0; i < n*n; i++) {
                for (int j = 0; j < 4; j++) {
                    int nx = i + dx[j];
                    if (i % n == 0 && j == 0) continue;
                    if(i % n == n - 1 && j == 1) continue;
                    if (nx < 0 || nx > n * n - 1) continue;
                    g[i].add(new Edge(nx, a[nx]));
                }
            }
            dijkstra();
            bw.write("#" + (t - T) + " " + d[n*n - 1] + "\n");bw.flush();
        }
        bw.close();
    }
    public static void dijkstra() {
        d[0] = 0;Arrays.fill(v, false);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        v[0] = true;
        pq.offer(new Edge (0, d[0]));
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            v[cur.v] = true;
            for (int i = 0; i < g[cur.v].size(); i++) {
                int to = g[cur.v].get(i).v;
                int cost = g[cur.v].get(i).w;
                if (!v[to] && d[to] > d[cur.v] + cost) {
                    d[to] = d[cur.v] + cost;
                    pq.offer(new Edge(to, d[to]));
                }
            }
        }
    }

    private static class Edge implements Comparable<Edge>{
        int v, w;
        Edge(int v, int w) {
            this.v = v;this.w = w;
        }
        @Override
        public int compareTo(Edge e) {
            return w < e.w ? -1 : 1;
        }
    }
}

설명

Copied to clipboard