글 읽기 - 캐슬 디펜스 28%에서 틀립니다. 반례가 어떤 게 있을까요?

jay531 3년 전 0

DFS로 궁수배치 후(Batch 함수) BFS로 사정거리 내 적들 탐색, 이후 각 궁수마다 제일 가까이 있는 적(중복인 경우 왼쪽 우선) 확인해서 일괄적으로 삭제(Shot 함수), 이후 한 칸씩 적들 내리기(Move 함수) 로 수행했습니다.

테스트 케이스 및 질문 게시판 반례 전부 통과했습니다. 어떤 게 잘못되었을까요...?

#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

struct MOV{
	int x, y;	
};

int N, M, D, ans;
int cunt;
int mat[16][16], mat2[16][16], mat3[16][16];
int arrow[3];
bool visited[16];
int target_search[16][16];
queue< pair<int, int> > target;

bool is_shooted[3];
bool end_flag;

MOV mov[4] = {{1,0}, {0,1}, {-1,0}, {0,-1}};

void print(){
	
	for(int i=0;i<=N;++i){
		for(int j=0;j<M;++j){
			cout << mat[i][j] <<" ";
		}
		cout << endl;
	}
	
	cout << endl;
	
}


void Move(){

	int cnt=0;

	for(int i=1;i<=N;++i){
		for(int j=0;j<M;++j){
			mat2[0][j] = 0;
			mat2[i][j] = mat[i-1][j];
			
			if(mat2[i][j] == 1){
				cnt++;
			}
			 
		}
	}
	
	if(cnt == 0){
		end_flag = true;
		return;	
	}
	
	
	for(int i=0;i<N;++i){
		for(int j=0;j<M;++j){
			mat[i][j] = mat2[i][j];		
		}
	}	
	
}

bool compare(pair<int, int> a, pair<int, int> b){
	
	if(a.first == b.first)
		return a.second > b.second;
	else
		return a.first > b.first;
	
}

void Shot(int arrow_idx, int depth){

	if(arrow_idx == depth){
		
		while(!target.empty()){
				
			int x = target.front().first;
			int y = target.front().second;
			target.pop();
			
//			cout << x<<", "<<y << " is target" << endl;
			
						
			if(mat[x][y] == 1){
				mat[x][y] = 0;
				cunt++;	
			}
			
		}
		
		return;
	}

	for(int i=0;i<N;++i){
		for(int j=0;j<M;++j){		
			target_search[i][j] = 0;
		}
	}		
	
	int cur_arrow = arrow[arrow_idx];
	
	
	queue< pair<int, int> > q;
	q.push(make_pair(N, cur_arrow));
	
	bool flag = false;
	
	while(flag == false){
		
		vector< pair<int, int> > competition;
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for(int i=0;i<4;++i){
		
			int nx = x + mov[i].x;
			int ny = y + mov[i].y;
						
			if(target_search[x][y] == D){
				
//				cout << "distance Exceed" << endl;
/*				
				for(int i=0;i<N;++i){
					for(int j=0;j<M;++j){				
						cout << target_search[i][j] << " ";
					}
					cout << endl;
				}
				
				cout << endl;
*/				
				flag = true;
				break;
			}			
			
			if(0<=nx && nx < N && 0<=ny && ny < M && target_search[x][y] < D){
				
				target_search[nx][ny] = target_search[x][y] + 1;
				
				if(mat[nx][ny] == 1){
					competition.push_back(make_pair(nx, ny));
					
				}
				
				q.push(make_pair(nx, ny));				
			}
										
		}
		
		int siz = competition.size();
		
		if(siz > 1){
			sort(competition.begin(), competition.end(), compare);	
		}
		
		if(siz >= 1){
			
			target.push(make_pair(competition[0].first, competition[0].second));
			flag = true;
		}
	}
	
	Shot(arrow_idx+1, depth);
	return;	
}

void Batch(int start, int cur, int depth){
	
	if(cur == depth){
		
		int sum=0;
		end_flag = false;
		
		for(int i=0;i<N;++i){
			for(int j=0;j<M;++j){		
				mat[i][j] = mat3[i][j];
			}
		}

//		cout << "New Arrow" << endl;
//		print();

		while(end_flag == false){				
			Shot(0, depth);	

//		cout << "AFTER SHOT" << endl;
//		print();			
			
			Move();

//		cout << "AFTER MOVE" << endl;
//		print();			
				
			sum+=cunt;
			cunt = 0;
							
//			cout << "sum: "<<sum<<endl;


			int tmp=0;	
			for(int i=N-1;i>=0;--i){
				for(int j=0;j<M;++j){			
					if(mat[i][j] == 1){
						tmp++;
						break;	
					}
				}
			}
			
			if(tmp==0){
				end_flag = true;	
			}


		}
		
		ans = max(ans, sum);
		cunt = 0;
				
		return;
	}
	
	for(int i=start;i<M;++i){
		
		if(visited[i] == false){
		
			visited[i] = true;
			mat[N][i] = 5;
			arrow[cur] = i;
			
			Batch(start, cur+1, depth);
			
			visited[i] = false;
			mat[N][i] = 0;	
			arrow[cur] = 0;
					
		}
		
	}
	
}

int main(){
	
	cin >> N >> M >> D;
	
	for(int i=0;i<N;++i){
		for(int j=0;j<M;++j){		
			cin >> mat[i][j];
			
			mat3[i][j] = mat[i][j];
		}
	}
	
	Batch(0, 0, 3);
	
	cout << ans << endl;
	
	return 0;	
}
/*

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

*/

qkrdbals1630 3년 전 1

"그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다."

가능한게 여러개일때 왼쪽에 있는지만 보면됩니다. 작성하신compare에서 우선순위를 보면 위아래가 왼쪽오른쪽보다 우선순위가 높게 되어있네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

캐슬 디펜스 28%에서 틀립니다. 반례가 어떤 게 있을까요?

jay531 3년 전 0

qkrdbals1630 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말