[백준/19236] 청소년 상어

물고기들이 움직이는 것은 map 이 4*4 밖에 안 되기 때문에 1차원 배열 16개로 직렬화 해서 시뮬레이션하고,

상어가 움직이는 것은 여러가지 경우의 수가 생길 수 있으므로 backtrackking 하면서 dfs 적용한다.

상어의 움직임을 dfs 적용하는 것만 간파하면 어렵지 않은 문제이다.

 

#include <iostream>
#include <vector>
using namespace std;
const int dx[] = {-1,-1,0,1,1,1,0,-1};
const int dy[] = {0,-1,-1,-1,0,1,1,1};
struct Node{
	int x,y,dir;
	Node(){}
	Node(int x,int y,int dir):x(x),y(y),dir(dir){}
};
Node fishs[17];
int map[5][5],total;
inline bool check(int x,int y){
	return x >= 0 && x < 4 && y >= 0 && y < 4;
}
inline int max(int a,int b){return a>=b?a:b;}
inline void __memcpy(int dest_map[5][5],int src_map[5][5],
	Node dest_fishs[17],Node src_fishs[17]){
	for(int i=1;i<17;i++) dest_fishs[i]=src_fishs[i];
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			dest_map[i][j]=src_map[i][j];
		}
	}
}
void mv_fishs(){
	for(int i=1;i<17;i++){
		Node &n = fishs[i];		
		int cd = n.dir;
		if( cd == -1 ) continue;
		int cx = n.x;
		int cy = n.y;
		for(int j=0;j<8;j++){
			int nd = (cd + j)%8;
			int nx = cx + dx[nd];
			int ny = cy + dy[nd];
			if( !check(nx,ny) || map[nx][ny]==0 ) continue;
			int num = map[nx][ny];
			Node &change = fishs[num];			
			change.x = cx;
			change.y = cy;
			n.x = nx;
			n.y = ny;
			n.dir = nd;
			map[nx][ny]=i;
			map[cx][cy]=num;
			break;
		}
	}
}
void dfs(int x,int y,int d,int sum){
	Node cp_fishs[17];
	int cp_maps[5][5];
	__memcpy(cp_maps,map,cp_fishs,fishs);
	mv_fishs();
	int nx = x;
	int ny = y;
	while(1){
		nx += dx[d]; ny += dy[d];
		if( check(nx,ny)){
			int num = map[nx][ny];
			if( num == -1 ) continue;
			int nd = fishs[num].dir;
			fishs[num].dir = -1;
			map[x][y]=-1;
			map[nx][ny]=0;
			dfs(nx,ny,nd,sum+num);
			map[nx][ny]=num;
			map[x][y]=0;
			fishs[num].dir = nd;
		}else{
			break;
		}
	}
	total=max(total,sum);
	__memcpy(map,cp_maps,fishs,cp_fishs);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			int num,dir;
			cin>>num>>dir;
			fishs[num] = Node(i,j,dir-1);
			map[i][j]=num;
		}
	}
	int num = map[0][0];
	int shk_dir = fishs[num].dir;
	fishs[num].dir = -1;
	map[0][0]=0;
	dfs(0,0,shk_dir,num);
	cout<<total<<"\n";
	return 0;
}