結果

問題 No.323 yuki国
ユーザー threepipes_s
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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>{
@Override
public 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());}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0