캐슬 디펜스
링크
풀이
2시간 걸렸다 .
일단 궁수 3명의 위치를 m크기의 열에서 어디에 놔야할지를 다 계산해야한다.
초기 맵(nXm)을 입력받으면서 n+1 째 행에 궁수를 3명 놓고 순열를 돌렸다.
그런 다음
죽여야하는 적의 좌표를 enemy 벡터에 넣은 후, 각 각 궁수들이 조건에 맞는 죽일 수 있는 적을 찾아
각 궁수가 죽일 수 있는 적의 위치가 겹칠 수 있으므로 중복 방지를 위해서 s set에 넣었다.
궁수가 죽일 수 있는 적을 모두 찾은 뒤 죽이고, 카운트를 세었다.
다음은 적들이 한칸 아래로 내려올 차례인데, 이때 적이 맵 밖으로 벗어날 수 있다. 이 적들을 따로 die 라는 변수에 담아 준 다음
카운트랑 다이 의 합이 죽여야하는 적의 수 len 과 같다면 게임은 끝.
아니면 리맵 후 ( 적을 한칸씩 내림) 다음 턴 시작.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <math.h>
#include <set>
using namespace std;
#define p pair<int,int>
set<p> s;
set<p>::iterator iter;
int n,m,d;
vector<vector<int>> remap(vector<vector<int>> map){
for(int i=0;i<m;i++){
for(int j=n-1;j>=0;j--){ //y
if(j==0){
map[j][i]=0;
continue;
}
map[j][i]=map[j-1][i];
}
}
return map;
}
void solve(int x,vector<p> enemy){
vector<p> e_pos; //p (x,y)
int e_d=1000000;
for(int i=0;i<enemy.size();i++){
int temp_d=abs(n-enemy[i].first)+abs(x-enemy[i].second);
if(temp_d>d) continue;
if(temp_d < e_d) {
e_d =temp_d;
e_pos.clear();
e_pos.push_back(p(enemy[i].second,enemy[i].first));
}
else if(temp_d == e_d) {
e_pos.push_back(p(enemy[i].second,enemy[i].first));
}
}
if(e_pos.size()!=0){
sort(e_pos.begin(),e_pos.end());
s.insert(p(e_pos[0].second,e_pos[0].first));
}
return ;
}
int main(){
int i,j,res=-1,cnt,die=0,len=0;
cin >> n >> m >>d;
vector<vector<int>> inter(n+1),map;
vector<p> enemy;
for(i=0;i<n+1;i++){
inter[i].resize(m);
if(i==n){
for(j=0;j<3;j++)
inter[i][j]=1;
continue;
}
for(j=0;j<m;j++)
cin >> inter[i][j];
}
do{
map=inter;
die=0,len=0,cnt=0;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(map[i][j]==1)
len++;
}
}
while(1){
s.clear();
enemy.clear();
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(map[i][j]==1)
enemy.push_back(p(i,j));
}
}
for(i=0;i<m;i++){
if(map[n][i]==1){
solve(i,enemy);
}
}
for(iter=s.begin();iter!=s.end();iter++){
int del_y =(*iter).first;
int del_x =(*iter).second;
for(j=0;j<enemy.size();j++){
if(enemy[j].first==del_y && enemy[j].second==del_x){
map[del_y][del_x]=0;
cnt++;
break;
}
}
}
for(i=0;i<m;i++){
if(map[n-1][i]==1)
die++;
}
if(len==die+cnt)
break; //게임 종료
map =remap(map); //다음 턴을 위해 적 한칸씩 내림
} //while(1)
if(cnt>res) res=cnt;
}while(prev_permutation(inter[n].begin(),inter[n].end()));
cout <<res<<endl;
}