BOJ. 19236번. 청소년상어

청소년 상어 문제는 그래도 그렇저럭 풀만했다...... 아닌가.....;;;;

물고기의 움직임 각각의 상태마다 상어가 움직이면서 그 map의 상태를 들고 다녀야 한다. 그 점만 유의해서 풀면 잘...해결할 수 있다......

www.acmicpc.net/problem/19236

19236번: 청소년 상어

package week8;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Day7BOJ19236 {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	static int n=4,ans=0;
	static int [] dy = {-1,-1, 0, 1, 1, 1, 0,-1};
	static int [] dx = { 0,-1,-1,-1, 0, 1, 1, 1};
//	static Fish[][] map = new Fish[4][4];
	
	static class Fish{
		int num,dir;
		boolean isDead;
		public Fish(int num,int dir,boolean isDead) {
			this.num = num;
			this.dir = dir;
			this.isDead = isDead;
		}
	}
	
	private static boolean checkBound(int y, int x) {
		return (y>=0 && y<n && x>=0 && x<n) ? true : false;
	}
	
	private static void rotate(int y, int x, Fish[][] map) {
		for(int nnum=1; nnum<=16; nnum++) {
	fish:  for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (map[i][j].num == nnum && !map[i][j].isDead) {
						int cnt =0;
						while(cnt<8) {
							int ddir = map[i][j].dir%8;
							int ny = i+dy[ddir];
							int nx = j+dx[ddir];
							if(!checkBound(ny,nx) || (y==ny && x==nx)) {
								map[i][j].dir++;
								cnt++;
								continue;
							}
							Fish temp = map[ny][nx];
							map[ny][nx] = map[i][j];
							map[i][j] = temp;
							break fish;
						}
					}
				}
			}
		}
	}
	
	private static void solution(int y,int x,int dir,int sum,Fish[][] map) {
		sum += map[y][x].num;
		dir = map[y][x].dir;
		map[y][x].isDead = true;
		
		ans = Math.max(ans, sum);
		rotate(y, x, map);
		
		for(int d=1; d<4; d++) {
			int ny = y + dy[dir]*d;
			int nx = x + dx[dir]*d;

			if(!checkBound(ny,nx)) break;
			if(map[ny][nx].isDead) continue;

			Fish mmap [][] = new Fish[4][4];
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					mmap[i][j] = new Fish(map[i][j].num,map[i][j].dir,map[i][j].isDead);
				}
			}
			solution(ny, nx, dir, sum, mmap);
		}
	}
	
	public static void main(String[] args) throws IOException {
		Fish[][] map = new Fish[4][4];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				int num = Integer.parseInt(st.nextToken());
				int dir = Integer.parseInt(st.nextToken())-1;
				map[i][j] = new Fish(num,dir,false);
			}
		}
		solution(0,0,0,0,map);
		System.out.println(ans);
	}
	
}