結果
問題 | No.323 yuki国 |
ユーザー |
![]() |
提出日時 | 2015-12-18 23:39:41 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,295 ms / 5,000 ms |
コード長 | 4,347 bytes |
コンパイル時間 | 2,376 ms |
コンパイル使用メモリ | 79,828 KB |
実行使用メモリ | 47,560 KB |
最終ジャッジ日時 | 2024-06-28 12:27:57 |
合計ジャッジ時間 | 22,223 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 32 |
ソースコード
import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.FileWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.BitSet;import java.util.HashMap;import java.util.PriorityQueue;import java.util.Queue;public class Main {public static void main(String[] args) throws NumberFormatException,IOException {Solve solve = new Solve();solve.solve();}}class Solve{int h, w;void solve() throws NumberFormatException, IOException{final ContestScanner in = new ContestScanner();Writer out = new Writer();h = in.nextInt();w = in.nextInt();int a = in.nextInt();int sy = in.nextInt();int sx = in.nextInt();int b = in.nextInt();int gy = in.nextInt();int gx = in.nextInt();char[][] map = new char[h][];for(int i=0; i<h; i++){map[i] = in.nextToken().toCharArray();}BitSet used = new BitSet(h*w*1111);Queue<Integer> qu = new PriorityQueue<>();final int[] dx = {1, 0, -1, 0};final int[] dy = {0, 1, 0, -1};qu.add(id(sy, sx, a));final int mask = (1<<6)-1;while(!qu.isEmpty()){int p = qu.poll();if(used.get(p)) continue;used.set(p);final int s = p>>12;final int y = (p>>6)&mask;final int x = p&mask;// System.out.println("("+x+","+y+","+s+")");for(int i=0; i<4; i++){final int ny = dy[i]+y;final int nx = dx[i]+x;if(out(ny, nx)) continue;// if(map[ny][nx]=='.'&&s==1) continue;int ns = s+(map[ny][nx]=='.'?-1:1);if(ns<=0||ns>=1111) continue;qu.add(id(ny, nx, ns));}}if(used.get(b<<12|gy<<6|gx)){System.out.println("Yes");return;}System.out.println("No");}int id(int y, int x, int s){return s<<12|y<<6|x;}int dist(int x1, int y1, int x2, int y2){return Math.abs(x1-x2) + Math.abs(y1-y2);}boolean out(int y, int x){return y<0||y>=h||x<0||x>=w;}}////class Pos implements Comparable<Pos>{// int id, x, y, s;// Pos(int x, int y, int s){// this.x = x;// this.y = y;// this.s = s;// id = y<<6|x;// }// @Override// public int compareTo(Pos o) {// return o.s-s;// }// @Override// public String toString() {// return "("+x+","+y+","+s+")";// }//}class MultiSet<T> extends HashMap<T, Integer>{@Overridepublic Integer get(Object key){return containsKey(key)?super.get(key):0;}public void add(T key,int v){put(key,get(key)+v);}public void add(T key){put(key,get(key)+1);}public void sub(T key){final int num = get(key);if(num==1) remove(key);else put(key, num-1);}}class Timer{long time;public void set(){time = System.currentTimeMillis();}public long stop(){return System.currentTimeMillis()-time;}}class Writer extends PrintWriter{public Writer(String filename) throws IOException{super(new BufferedWriter(new FileWriter(filename)));}public Writer() throws IOException{super(System.out);}}class ContestScanner {private BufferedReader reader;private String[] line;private int idx;public ContestScanner() throws FileNotFoundException{reader = new BufferedReader(new InputStreamReader(System.in));}public ContestScanner(String filename) throws FileNotFoundException{reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}public String nextToken() throws IOException {if (line == null || line.length <= idx) {line = reader.readLine().trim().split(" ");idx = 0;}return line[idx++];}public String readLine() throws IOException{return reader.readLine();}public long nextLong() throws IOException, NumberFormatException{return Long.parseLong(nextToken());}public int nextInt() throws NumberFormatException, IOException{return (int) nextLong();}public double nextDouble() throws NumberFormatException, IOException{return Double.parseDouble(nextToken());}}