글 읽기 - 5일쨉니다. 게시판 반례 다 돌아갑니다. 21%에서 계속 틀립니다.

jay531 2년 전 0

게시판 반례 다 돌아갑니다. 21%에서 계속 틀립니다...제발 이유 좀 설명해주세요

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
#define MAX 17

struct mov{
	int x, y;
};

int board[MAX][MAX], board_bck[MAX][MAX];
bool archer_visit[MAX];
mov archer_location[3], archer_location_bck[3];
int num_eneny, num_eneny_bck;
mov kill_enemy[3];
int kill_count;
int first_enemy_row;
int ans;

void backup(int N, int M){
	for(int i = 0; i<N; ++i){
		for(int j = 0; j<M; ++j)
			board[i][j] =  board_bck[i][j];
	}
}

void attack(int N, int M, int D){
// testprint(N, M);

	if(num_eneny==0 || N==first_enemy_row){

		return ;
	}

	mov m[3] = { {0,-1},{-1,0},{0,1} };		// < ^ >
	

	for(int h = 0; h<3; ++h){
		queue< pair<int,int> > q;
		bool enemy_visited[MAX][MAX] = {0, };

		q.push(make_pair(archer_location[h].x-1,archer_location[h].y));
// printf("archer? (%d,%d)\n", q.front().first, q.front().second);
		while(q.empty()==false){
			

			int cur_x = q.front().first;
			int cur_y = q.front().second;
			enemy_visited[cur_x][cur_y] = true;
			q.pop();
// printf("current : (%d,%d)\n", cur_x,cur_y);
			if(board[cur_x][cur_y]==1){
				kill_enemy[h] = {cur_x,cur_y};
// cout << "^^" << endl;
				break;
			}

			for(int i = 0; i<3; ++i){
				int nx = cur_x + m[i].x;
				int ny = cur_y + m[i].y;

				if(nx>=0 && ny>=0 && nx<N && ny<M && enemy_visited[nx][ny]==false && abs(cur_x-nx)+abs(cur_y-ny)<D){
					enemy_visited[nx][ny] = true;
					q.push(make_pair(nx,ny));
				}
			}
		}
	}
	for(int h = 0; h<3; ++h){
		int cur_x = kill_enemy[h].x;
		int cur_y = kill_enemy[h].y;
// printf("(%d,%d)\n", cur_x, cur_y);
		if(board[cur_x][cur_y]==1){
			board[cur_x][cur_y] = 0;
			++kill_count;
			--num_eneny;
// cout << "	$$$$ kill!! " << kill_count << "번째" << endl;
		}

		kill_enemy[h] = {-1,-1};
		archer_location[h].x = N-1;
	}
// testprint(N, M);
	for(int j = 0; j<M; ++j){
		board[N-1][j] = board[N][j];
	}
	attack(--N, M, D);

}

void disposition_archers(int N, int M, int D, int start, int depth){
	if(depth == 3){

		for(int h = 0; h<3; ++h)
			archer_location[h] = archer_location_bck[h];

		attack(N, M, D);
		num_eneny = num_eneny_bck;
// cout << "$$$$$$$ kill count : " << kill_count << endl;
		if(ans < kill_count)
			ans = kill_count;
		kill_count = 0;
		backup(N, M);
		return ;
	}
	for(int j = start; j<M; ++j){
		if(archer_visit[j]==false){
			board[N][j] = 2;
			archer_visit[j] = true;
			archer_location[depth] = {N,j};
			archer_location_bck[depth] = {N,j};
			depth++;
			disposition_archers(N, M, D, j, depth);
			depth--;
			archer_visit[j] = false;
			board[N][j] = -1;
		}
	}
}

int main(){

	int N, M, D;
	cin >> N >> M >> D;

	bool first_enemy_flag = false;
	for(int i = 0; i<N; ++i){
		for(int j = 0; j<M; ++j){
			cin >> board[i][j];
			board_bck[i][j] = board[i][j];

			if(board[i][j] && first_enemy_flag == false){
				first_enemy_row = i;
				first_enemy_flag = true;
			}

			if(board[i][j]==1){
				++num_eneny;
				++num_eneny_bck;
			}
		}
	}
	for(int j = 0; j<M; ++j){
		board[N][j] = -1;
	}

// cout << endl;

	for(int h = 0; h<3; ++h){
		kill_enemy[h] = {MAX-1,MAX-1};
	}
	disposition_archers(N, M, D, 0, 0);

	cout << ans << endl;

	return 0;
}

lg960214 1년 전 5

7 6 2

0 1 1 0 1 0

1 1 0 1 0 0

1 0 1 0 0 1

0 1 0 0 1 0

1 0 0 1 0 1

0 0 1 0 1 1

0 1 0 1 1 0

답은 18입니다

21퍼 틀린 분들은 19 나올거예요

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

문제

문제

출처

ICPC

5일쨉니다. 게시판 반례 다 돌아갑니다. 21%에서 계속 틀립니다.

jay531 2년 전 0

lg960214 1년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말