白駿2447:星を撮る-10

11031 ワード
cpp 分割征服 テキストリンク
https://www.acmicpc.net/problem/2447

1.近接

  • を使って鬼を救うように要求したので、分割で征服して接近.
  • N全体を表現するために、最終的には3の平方数の時のパターンが繰り返される.
  • Nを3に分割し続け、N*Nから中間をクリアするプロセスを繰り返す必要があります.
  • 以前の問題とは異なり、最小サイズは3*3形状であるため、サイズが3未満になるまで繰り返す.
    △先の質問では、不一致などの条件で繰り返し、すべて確認すれば終わります.

    • 2.私の回答

    #include <iostream>
#include <cstring>
#define MAX 2200
using namespace std;

int n;
bool star[MAX][MAX];

void divide(int x, int y, int size) {
	int blanksize = size / 3;
	for (int i = x+ blanksize; i < x+ blanksize *2; i++) {
		for (int j = y+ blanksize; j < y + blanksize *2; j++) {
			star[i][j] = false;
		}
	}
}

void check(int x, int y, int size) {
	if (star[x][y]) {
		divide(x, y, size);

		int newsize = size / 3;
		if (newsize == 1) return;
		for (int i = x; i <= x + newsize*2; i+=newsize) {
			for (int j = y; j <= y + newsize*2; j+=newsize) {
				check(i, j, newsize);
			}
		}
	}
}

void printStar() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (star[i][j]) cout << "*";
			else cout << " ";
		}
		cout << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		memset(star[i], true, n);
	}
	

	check(0, 0, n);
	printStar();
	return 0;
}
    119.水を探す
    huffmanコード---zoj_1117