AOJ-2253: Brave Force Story
解法
タイトル通りにBFSする。Javaで配列をHashSetに突っ込もうとして引っかかった。
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; public class Main{ int dy[] = {1,0,-1,-1,0,1}; int dx[] = {0,-1,-1,0,1,1}; class Position{ int x, y; Position(int _x, int _y){ this.x = _x; this.y = _y; } public boolean equals(Object a){ return a instanceof Position && ((Position)a).x == this.x && ((Position)a).y == this.y; } public int hashCode(){ return java.util.Arrays.hashCode(new int[]{this.x, this.y}); } } class State{ int x, y, dist; State(int _x, int _y, int _d){ this.x = _x; this.y = _y; this.dist = _d; } } void run(){ Scanner in = new Scanner(System.in); for(;;){ int t = in.nextInt(), n = in.nextInt(); if(n==0 && t==0) return ; Set<Position> blocks = new HashSet<Position>(); for(int i=0; i<n; i++){ blocks.add(new Position(in.nextInt(), in.nextInt())); } Position start = new Position(in.nextInt(), in.nextInt()); System.out.println(solve(blocks, t, start)); } } int solve(Set<Position> blocks, int t, Position start){ Set<Position> visited = new HashSet<Position>(); visited.add(start); Queue<State> que = new LinkedList<State>(); que.add(new State(start.x, start.y, 0)); while(!que.isEmpty()){ State tp = que.poll(); Position cur = new Position(tp.x, tp.y); int dist = tp.dist; if(dist >= t){ continue; } for(int k=0; k<6; k++){ Position next = new Position(cur.x + dx[k], cur.y + dy[k]); if(!visited.contains(next) && !blocks.contains(next)){ visited.add(next); que.add(new State(next.x, next.y, dist + 1)); } } } return visited.size(); } public static void main(String[] args){ new Main().run(); } }