結果
| 問題 | No.2064 Smallest Sequence on Grid |
| ユーザー |
 watarimaycry2
|
| 提出日時 | 2022-09-02 22:37:06 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,700 bytes |
| コンパイル時間 | 4,370 ms |
| コンパイル使用メモリ | 84,304 KB |
| 実行使用メモリ | 423,212 KB |
| 最終ジャッジ日時 | 2024-11-16 04:48:39 |
| 合計ジャッジ時間 | 38,367 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 TLE * 2 |
ソースコード
import java.util.*; import java.io.*; import java.math.*;public class Main{//見なくていいよ ここから------------------------------------------static class InputIterator{ArrayList<String> inputLine = new ArrayList<>(1024);int index = 0; int max; String read;InputIterator(){try{BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "UTF-8"));while((read = br.readLine()) != null){inputLine.addAll(Arrays.asList(read.split(" ")));}}catch(IOException e){}max = inputLine.size();}boolean hasNext(){return (index < max);}String next(){if(hasNext()){return inputLine.get(index++);}else{throw new IndexOutOfBoundsException("There is no more input");}}}static HashMap<Integer, String> CONVSTR = new HashMap<>();static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.static PrintWriter out = new PrintWriter(System.out);static void flush(){out.flush();}static void myout(Object t){out.println(t);}static void myerr(Object... t){System.err.print("debug:");System.err.println(Arrays.deepToString(t));}static String next(){return ii.next();}static boolean hasNext(){return ii.hasNext();}static int nextInt(){return Integer.parseInt(next());}static long nextLong(){return Long.parseLong(next());}static double nextDouble(){return Double.parseDouble(next());}static ArrayList<String> nextCharArray(){return myconv(next(), 0);}static ArrayList<String> nextStrArray(int size){ArrayList<String> ret = new ArrayList<>(size);for(int i = 0; i < size; i++){ret.add(next());}return ret;}static ArrayList<Integer> nextIntArray(int size){ArrayList<Integer> ret = new ArrayList<>(size);for(int i = 0; i < size; i++){ret.add(Integer.parseInt(next()));}return ret;}static ArrayList<Long> nextLongArray(int size){ArrayList<Long> ret = new ArrayList<>(size);for(int i = 0; i < size; i++){ret.add(Long.parseLong(next()));}return ret;}@SuppressWarnings("unchecked")static String myconv(Object list, int no){//only joinStringBuilder sb = new StringBuilder("");String joinString = CONVSTR.get(no);if(list instanceof String[]){return String.join(joinString, (String[])list);}else if(list instanceof long[]){long[] tmp = (long[])list;if(tmp.length == 0){return "";}sb.append(String.valueOf(tmp[0]));for(int i = 1; i < tmp.length; i++){sb.append(joinString).append(String.valueOf(tmp[i]));}return sb.toString();}else if(list instanceof int[]){int[] tmp = (int[])list;if(tmp.length == 0){return "";}sb.append(String.valueOf(tmp[0]));for(int i = 1; i < tmp.length; i++){sb.append(joinString).append(String.valueOf(tmp[i]));}return sb.toString();}else if(list instanceof ArrayList){ArrayList tmp = (ArrayList)list;if(tmp.size() == 0){return "";}sb.append(tmp.get(0));for(int i = 1; i < tmp.size(); i++){sb.append(joinString).append(tmp.get(i));}return sb.toString();}else{throw new ClassCastException("Don't join");}}static ArrayList<String> myconv(String str, int no){//only splitString splitString = CONVSTR.get(no);return new ArrayList<String>(Arrays.asList(str.split(splitString)));}static ArrayList<String> myconv(String str, String no){return new ArrayList<String>(Arrays.asList(str.split(no)));}public static void main(String[] args){CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");solve();flush();}//見なくていいよ ここまで------------------------------------------//このコードをコンパイルするときは、「-encoding UTF-8」を指定することstatic void solve(){//ここがメイン関数int H = nextInt();int W = nextInt();Node[][] list = new Node[H][W];for(int i = 0; i < H; i++){String s = next();for(int j = 0; j < W; j++){char c = s.charAt(j);list[i][j] = new Node(i, j, c);}}ArrayDeque<Edge> queue = new ArrayDeque<>();queue.add(new Edge(0, 0));list[0][0].access = true;while(queue.size() > 0){ArrayList<Edge> nx = new ArrayList<>();while(queue.size() > 0){Edge tmp = queue.pollFirst();int y = tmp.y;int x = tmp.x;if(y < H - 1){nx.add(new Edge(y + 1, x));}if(x < W - 1){nx.add(new Edge(y, x + 1));}}if(nx.size() == 0){break;}char ok = Character.MAX_VALUE;for(Edge nxe : nx){if(Character.compare(ok, list[nxe.y][nxe.x].S) >= 1){ok = list[nxe.y][nxe.x].S;}}for(Edge nxe : nx){if(ok == list[nxe.y][nxe.x].S && !list[nxe.y][nxe.x].access){list[nxe.y][nxe.x].access = true;queue.add(nxe);}}}int lastY = H - 1;int lastX = W - 1;char[] output = new char[H + W - 1];int lastIndex = H + W - 2;while(true){output[lastIndex] = list[lastY][lastX].S;lastIndex--;if(lastY == 0 && lastX == 0){break;}if(lastY > 0 && lastX > 0){if(list[lastY - 1][lastX].access){lastY--;}else{lastX--;}}else if(lastY > 0){lastY--;}else{lastX--;}}myout(new String(output));}//メソッド追加エリア ここからstatic class Node implements Comparable<Node>{char S;int y;int x;boolean access = false;Node(int y, int x, char S){this.S = S;this.y = y;this.x = x;}public int compareTo(Node ato){return Character.compare(this.S, ato.S);}}static class Edge{int y;int x;Edge(int y, int x){this.x = x;this.y = y;}}//メソッド追加エリア ここまで}