BOJ 2045 - 마방진
수학적으로 방정식을 풀 수도 있겠지만 최대 수가 20000이라는 점을 이용해서 브루트포스를 돌려도 된다.
각 줄의 합이 라는 점을 파악하자.
각 줄에 대해 9번정도씩 순회해보면 각 시도마다 무조건 이 하나만 있는 줄이 있다.
그럼 그 줄의 0을 로 만들어주고 마지막에 크로스 체크까지 하는것이다.
void solve() {
vvi bb(3, vi(3));
fv2(bb);
vector<vector<pi>> lines = {
{ {0, 0}, {0, 1}, {0, 2}},
{ {1, 0}, {1, 1}, {1, 2}},
{ {2, 0}, {2, 1}, {2, 2}},
{ {0, 0}, {1, 0}, {2, 0}},
{ {0, 1}, {1, 1}, {2, 1}},
{ {0, 2}, {1, 2}, {2, 2}},
{ {0, 0}, {1, 1}, {2, 2}},
{ {0, 2}, {1, 1}, {2, 0}},
};
for(int s=3;s<=60000;s++) {
auto b = bb;
for(int _ =0;_<9;_++){
for(const auto& line: lines) {
int zero_cnt = 0, sum = 0;
pi zero_pos;
for(auto&[y,x]: line) {
if(b[y][x] == 0) zero_cnt++, zero_pos = mp(y,x);
sum += b[y][x];
}
if(zero_cnt == 1) {
b[zero_pos.fi][zero_pos.se] = s-sum;
}
}
}
int f = 1;
for(const auto& line: lines ){
int sum = 0;
for(auto&[y,x]: line) {
sum += b[y][x];
if(b[y][x] <= 0 || b[y][x] > 20000) f=0;
}
if(sum^s){ f=0;break;}
}
if(f) {
for(int y=0;y<3;y++) {
for(int x = 0;x<3;x++){
cout << b[y][x] << ' ';
}
cout << endl;
}
return;
}
}
}
Comments