https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
분류 : BFS
더보기
import java.io.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
public static MyScanner sc = new MyScanner();
static int[] Hx = {-2,-1,1,2,2,1,-1,-2};
static int[] Hy = {-1,-2,-2,-1,1,2,2,1};
static int[] dx = {1,0,-1,0};
static int[] dy = {0,-1,0,1};
static int K,W,H,map[][];
static boolean[][][] visited;
public static void main(String[] args) throws IOException {
K = sc.nextInt();
W = sc.nextInt();
H = sc.nextInt();
map = new int[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
map[i][j] = sc.nextInt();
}
}
visited = new boolean[201][201][31];
int ans = BFS();
out.println(ans);
out.flush();
}
private static int BFS() {
Queue<Point> q = new LinkedList<Point>();
visited[0][0][K]=true;
q.offer(new Point(0,0,K));
int depth=0;
while(!q.isEmpty())
{
int size = q.size();
for(int sz =0;sz<size;sz++)
{
Point p = q.poll();
int x = p.x;
int y = p.y;
int move = p.move;
if(x == H-1 && y == W-1){
return depth;
}
if(move>0){
for(int h=0;h<8;h++)
{
int Hx1 = x+Hx[h];
int Hy1 = y+Hy[h];
if(Hx1<0 || Hy1<0 || Hx1>=H || Hy1>=W) continue;
if(map[Hx1][Hy1]==0 && !visited[Hx1][Hy1][move-1])
{
visited[Hx1][Hy1][move-1]=true;
q.offer(new Point(Hx1,Hy1,move-1));
}
}
}
for(int M =0;M<4;M++){
int Mx1 = x+dx[M];
int My1 = y+dy[M];
if(Mx1<0 || My1<0 || Mx1>=H || My1>=W) continue;
if(map[Mx1][My1]==0 && !visited[Mx1][My1][move]){
visited[Mx1][My1][move]=true;
q.offer(new Point(Mx1,My1,move));
}
}
}
depth++;
}
return -1;
}
}
class Point{
int x,y,move;
Point(int x, int y , int move){
this.x = x;
this.y = y;
this.move = move;
}
}
BFS 문제이고 나이트의 이동 문제와 비슷해 보여서 쉽게 풀릴 줄 알았다.
계속 틀리길래 뭐지.. 하고서 봤더니 가로,길이 입력의 순서가 바뀌어서 계속 고민했다...
그러다 질문 검색에 있는 많은 반례도 집어 넣는데 이상하게 케이스 하나가 안돼서 멘붕...
그러다 문제점을 발견했고 해결 완료.. 문제를 제대로 읽읍시다
'PS' 카테고리의 다른 글
[BOJ]1874번 : 스택 수열 (0) | 2017.04.17 |
---|---|
[BOJ]1931번 : 회의실 배정 (0) | 2017.04.17 |
[BOJ]9373번 : 복도 뚫기 (0) | 2017.04.06 |
[BOJ1005번 : ACM Craft (0) | 2017.04.04 |
[BOJ]10422번 : 괄호 (0) | 2017.04.03 |