[伯俊C+]は24727の志勇です~

2022年、延世大学の新学期の迎新プログラミングコンテストのオープンテストE問題だ.

質問する

延世(ヨンセ)大学は2022年から人工知能融合大学を新設し、工学部に所属していたコンピューター科学科を同学院に入学させた.しかし、人工知能融合大学の建物が完成していないため、学生たちは工事館を使っている.
そこで、工科大学の他の学科の学生はコンピュータ科学部の学生を笑い始めました!
怒ったコンピューター科学学部の学生は、他の工科大学の学生を近づけないようにバリアを設置した.しかし、うっかり他の学科の空間を侵害し、怒った学生と教授たちがバリケードを破壊した!
最終的に長時間の協議を経て、工科大学側はまず必要な空間の大きさとコンピュータ科学学部の必要な空間の大きさを提出し、それからそれぞれの大きさを保証してバリアを設置することに同意した.
工事館はN×NN\times NN×Nの大きさの正方形の形で、バリケードを設置した後、コンピュータ科学部の空間と工科大学の空間は一緒に接続すべきではないが、それぞれの空間は一緒に接続すべきである.
ここで「接続」とは、ある空間が上下左右に隣接していることを意味する.
例えば、下図では、左のAAA空間はBBB空間に接続されず、右のAAA空間はBBB空間に接続されている.

また,競合を防止するためには,正確なコミットサイズの空間しか提供できない.
工学館の大きさとコンピュータ科学部、工科大学側が提出する空間の大きさが与えられた場合、どのような方法で空間を割り当てるべきでしょうか.

入力

1行目はNNN(1≤N≤100)(1\le N\le 100)(1≤N≤100) 
第2列はコンピュータ科学系に必要な空間の大きさCCC,その他工科大学系に必要な空間の大きさEEEである.(1≤C,E≤N2)(1\le C, E\le N ^ 2)(1≤C,E≤N2) 

しゅつりょく

所定の条件に従って空間を分割できない場合は、−1が出力される.
所定の条件に従って空間を分割できる場合、第1行に1を出力する.また,2行目からNNN行間に空間を割り当てた結果を出力する.そのうち1はコンピューター科学部の空間,2は工科大学の空間,0はバリアである.

に答える

多くの空間分離の問題に遭遇しました
今回の質問を見て、私が確信したのは、
空間を2つの部分に分割する場合、対角線分割が最適です.

A空間.つまり、まずコンピューター科学と空間を上図の順に埋め尽くし、残りの空間に一コマ空けて、工科大学生に入れればいいのです.

これはコンピュータ科学部(A)のレイアウトコードです.
cnt aの値は

Aから紫色で表記された箇所までの数を置くことができます.
要するにcnt a>0のコードで配置する.
cnt a=0人、13番目の格子は1回だけ、
それから緑の矢印に沿ってAのコードを置きます.
Aの次はBで、
Aが未配置の空白の場合、すべての座標をナビゲートします.

この方向ベクトルをその位置+に対して右下左上
Aがなければ、その位置にBを置きます.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
//n, c, e : 입력값
//cnt: 공과대학생수를셀것
//map: 학생들의 배치도
int n, c, e, cnt, ** map; 
int dx[4] = { 0, 1, 0, -1 }; //우 하 좌 상 순서
int dy[4] = { 1, 0, -1, 0 };

int main(void) {
	scanf("%d%d%d", &n, &c, &e);
	cnt = e; 
	if (c > n * n) { //컴퓨터공학과 학생수가 맵보다크면
		printf("-1");
		return 0;
	}
	map = new int* [n];
	//맵 생성, 초기화
	for (int i = 0; i < n; i++) {
		map[i] = new int[n];
		for (int j = 0; j < n; j++)
			map[i][j] = 0; //빈공간 즉 바리게이트
	}

	//컴퓨터과학과 학생(A)을 배치
	int x = 0, y = 0, gap1 = 1, gap2 = 1, cnt_a = 0;
	for (int k = 1; k <= n; k++) cnt_a += k;
	while (c--) {
		map[x][y] = 1; //현재위치에 A그룹을 설치
		cnt_a--;
		if (cnt_a > 0) {
			x -= 1; y += 1; //우상단방향으로 설치
			if (x < 0) {
				x = gap1; y = 0;
				gap1++;
			}
		}
		else if (cnt_a == 0) {
			x = 1; y = n - 1;
		}
		else {
			x += 1; y -= 1; //좌상단으로설치
			if (y < gap2) {
				gap2++;
				x = gap2;  y = n - 1;
			}
		}
		
	}

	int res = 0;

	//공과대학생(B )을 배치
	for (int i = 0; i < n; i++) {
		if (cnt == 0) break;
		for (int j = 0; j < n; j++) { //현재위치 i,j 탐색
			if (cnt == 0) break;
			if (map[i][j] == 1) continue; //이미 컴퓨터과학과공간이면 제외
			bool isBlank = true; //빈공간인가? => 공과대학생공간 설치가 가능한가?
			for (int k = 0; k < 4; k++) { //현재위치 i,j에서 상하좌우를 탐색
				int xx = i + dx[k];
				int yy = j + dy[k];
				if (xx < 0 || y < 0 || n == xx || n == yy) continue; //맵크기를 벗어나면 제외
				if (map[xx][yy] == 1) { //i,j 기준 상하좌우에 컴퓨터과학과공간이 설치되있으면
					isBlank = false; //빈공간이 아님
					break; //상하좌우 탐색종료
				}
			}
			if (isBlank) {
				map[i][j] = 2; //현재위치를 공과대학생공간으로 기록
				res++;
				cnt--; //공과대학생수 카운트
			}
		}
	}

	if (res < e)
		printf("-1");
	else {
		printf("1\n");
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				printf("%d", map[i][j]);
			}
			printf("\n");
		}
	}

	return 0;
}