[๋ฐฑ์ค c++] 1030 ํ๋ ํํ๋ฉด (๊ณจ3)
๐ ๋ฌธ์
https://www.acmicpc.net/problem/1030
1030๋ฒ: ํ๋ ํ ํ๋ฉด
์ฒซ์งธ ์ค์ 7๊ฐ์ ์ ์ s, N, K, R1, R2, C1, C2๊ฐ ์ฃผ์ด์ง๋ค.
www.acmicpc.net
๊ฒฐ๋ก ๋ถํฐ ๋งํ์๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋ฌ๋ค...
ํ์๋ ๋ณด๋๋ฅผ ๊ด์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์๋ค.
๋ณด๋์ ๋ชจ๋ ํ๋ ํ ํ๋ฉด ๊ตฌ์กฐ๋ฅผ ๋ค ํ์ํ๋ฉด์ R1, R2, C1, C2 ๋ด์ ํด๋น๋๋ฉด ์ถ๋ ฅํ ์ ์๋๋ก ์ถ๋ ฅ ์ด์ฐจ์ ๋ฐฐ์ด์ ์ ์ธํ์ง๋ง ์ด ๋ฐฉ๋ฒ์ด ์๋ ๋ฏ ํ๋ค.
๋ค๋ฅธ ๋ธ๋ก๊ทธ ๊ธ์ ์ฐธ์กฐํด๋ณด๋ ํด๋น R1, R2, C1, C2๋ฅผ ํ์ํ๋ฉด์ ํด๋น ์นธ๋ค์ด ์์น ๋๋ ์นธ์ธ์ง๋ฅผ ํ์ธํ๋ค...
ใ ใ ์ฒ์๋ถํฐ ์ ๊ทผ์ ์ ๋ชปํ ๊ฒ์ด์๋ค.
๋ฌธ์ ํ๋ฉด์ ๋ถ๋ถ๋ง ์ถ๋ ฅํ๋ผ๋ ์กฐ๊ฑด์ ๋ณด๋ฉด ๊ทธ๋ ๊ฒ ์๊ฐํ์ด์ผํ๋๋ฐ.....
๋ค๋ฅธ ๋ถ๋ค ์ฝ๋๋ฅผ ๋ณด๊ณ ํต๊ณผ๋ฅผ ํ๋ค.
#include <iostream>
#include <cmath>
using namespace std;
int S, N, K;
int R1, C1, R2, C2; // (C1,R1) ~ (C2,R2) ๊ณ์ฐํ๊ธฐ
int MAX;
int outSizeY, outSizeX;
//์ถ๋ ฅ ๊ฐ
bool board[51][51];
//์ฒ์์ ์ ๋๋ก ์ ๊ทผํ๋ ๊ฒ์ด ๋ ์ค์ํ๋ค
void Recursive(int Nsize, int t, int X, int Y) {
//Nsize ํ์ฌ ์ฒดํฌํ๊ณ ์๋ ๋๋๋ ค๊ณ ํ๋ ๋ฐ์ค์ ํฌ๊ธฐ
//t ํ์ฌ ์๊ฐ
//X, Y ํด๋น ๋ฐ์ค๊ฐ ์์ํ๋ ์ผ์ชฝ ์์ ์ฝ๋
cout << Nsize << " " << t << " " << X << " " << Y << "ํ์์ค" << endl;
//Ksize ์ ์ฌ๊ฐํ์ ์ค๊ฐ ๊ฐ์ ํฌ๊ธฐ๋ฅผ scale์ ๋ฐ๋ผ์ ๊ณ์ฐํ๊ธฐ
int Ksize = K * pow(N, S - t);
//๊ฐ์ด๋ฐ ๊ณ์ฐ => ํด๋น Nsize์ ์ ์ฌ๊ฐํ ๊ธฐ์ค ์ค๊ฐ ๊ฐ์ ์, ์๋ ๊ฐ ๊ณ์ฐ
int middleL = (Nsize - Ksize) / 2; // ์์
int middleR = (Nsize + Ksize) / 2; // ํฐ
//cout << Ksize << " " << middleL << " " << middleR << endl;
//๋ด๊ฐ ์ถ๋ ฅํ๋ ๋ถ๋ถ์ด
//๊ฐ์ด๋ฐ์ ํด๋นํ๋ ์นธ์ด ํด๋น ์นธ์ ํด๋นํ๋์ง ํ์ธ.
for (int i = middleL + Y; i < middleR + Y; i++) {
if (R1 > i || R2 < i) continue;
for (int j = middleL + X; j < middleR + X; j++) {
if (C1 > j || C2 < j) continue;
//๋ฒ์์ ํด๋นํ๋ค๋ฉด ์์น ํ๊ธฐ
board[i - R1][j - C1] = true;
}
}
//์ธ๋ถํ ์ข
๋ฃ ์, return 0
if (S == t) return;
//์ธ๋ฑ์ค ์ธ๋ถํ ํ์, ๋ถํ ์ ๋ณตํ๊ธฐ
//์ผ์ชฝ ์
int NsizeDiv = Nsize/N;
//์์ชฝ ๋ผ์ธ ํ์
if(C1 < X + Nsize && R1 < Y ){
for (int i = Y; i < Y + middleL; i+= NsizeDiv) {
for (int j = X; j < X + Nsize ; j+= NsizeDiv)
Recursive(Nsize / N, t + 1, j, i);
}
}
//๊ฐ์ด๋ฐ ํ์
for (int i = Y + middleL; i < Y + middleR; i+= NsizeDiv) {
//์ผ์ชฝ ํ์
for (int j = X; j < X + middleL; j += NsizeDiv ) {
Recursive(Nsize / N, t + 1, j, i);
}
//์ค๋ฅธ์ชฝ ํ์
for (int j = X + middleR; j < X + Nsize; j+= NsizeDiv) {
Recursive(Nsize / N, t + 1, j, i);
}
}
//์๋์ชฝ ๋ผ์ธ ํ์
for (int i = Y + middleR; i < Y + Nsize; i+= NsizeDiv) {
for (int j = X; j < X + Nsize; j+= NsizeDiv) {
Recursive(Nsize / N, t + 1, j, i);
}
}
}
int main() {
//input
cin >> S >> N >> K >> R1 >> R2 >> C1 >> C2;
outSizeY = R2 - R1 + 1;
outSizeX = C2 - C1 + 1;
MAX = pow(N, S);
//Recursive
Recursive(MAX, 1, 0, 0);
//output
for (int i = 0; i < outSizeY; i++) {
for (int j = 0; j < outSizeX; j++) {
cout << board[i][j];
}
cout << endl;
}
return 0;
}