[伯俊C]製作23562

質問する

2021年、韓国人の基本的な素質を作るのに必死だった.私たちは前に置いたn×mn\times mn×m四角い紙に力を入れて描きたい.
形状はk×kk\times kk×k 7個の正方形を貼り合わせとして定義する.以下、k=1、k=2 k=1、k=2 k=1、k=2 k=2のときのジッタ形状を示す.

成らない例は以下の通りです.

四角い紙のいくつかの格子はすでに黒に塗られている.白い格子を黒く塗る費用はaaa、黒い格子を白い格子に塗る費用はbbbです.黒い格子の最小コストを求めるプログラムを作成します.
形状の位置や大きさには制限はありませんが、反転や回転はできませんし、母紙から離れることもできません.また、すべての黒いチェックボックスは、[ジッタ](Jiggle)シェイプに含まれないチェックボックスはすべて白でなければなりません.

入力

第1行は、四角紙の大きさn,mn,mn,mを与える.
2行目は、セルの色を変更する費用a、ba、ba、bを示します.
次のnnn行では、長さmmmの文字列が与えられます.#黒塗りの格子白い格子を表す.

しゅつりょく

1行目に、ジグルシェイプを生成する最小コストを印刷します.
https://www.acmicpc.net/problem/23562

に答える

その大きさは3 kx 3 k(k=1,2,"")であるからである.kをマッピングサイズに制限します.
座標(x,y)を基準座標として、右・下3キロの座標(xx,yy)をナビゲートします.

(xx,yy)利用可能な空間(3 kx 3 k)ですべての白->黒のコストを計算する.

同時に,3 kx 3 k空間ですべての黒の数を計算した.

数え終わると、黒い数字(3 kx 3 k)が表示され、すべてを白くする必要があるため、コストを計算する必要があります.

実際に白を必要とする空間(41~52行)では、上記の第1の過程で白を強制的に交換したため、再度この費用を差し引く.

また、ブラック->ホワイトコスト.

最後に、これが最適値である場合、resに格納され、最終的に決定されたres出力が格納される.
ここのミスは、
最初に入力した#と.bとaの値をmapに代入するのは大きなミスです.一日二日、そうだ、なぜ不確定なのか、a=bの反例を確認した.
bは−1,aは−2に代わり,黒格子と白格子を明確に区別した.

したがって、赤い部分もすべて=a,=bと書くのが間違いです.
早く1、2段階スキップしようとしたら、エラーが発生しました.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
//맵크기 n x m 
//map : 검은칸은 -1 흰색칸은 -2값대입
//a : 흰색을 검정으로 칠하는비용
//b : 검정을 흰색으로 칠하는비용
//blackCnt : 모든 검은칸갯수 (ㄷ자에 모든 검은칸이 포함되어야한다.)
int n, m, a, b, **map, blackCnt=0;
void func();
void input();

void func() {
	input();
	int maxSize = n >= m ? m : n; //n과 m중 최솟값
	int res = 0x7fffffff;
	for (int k = 1; 3 * k <= maxSize; k ++) {
		
		//시작위치 x,y(좌상단좌표)를 정함
		int size = 3 * k;
		for (int x = 0; x + size <= n; x++) { //올바른 좌표범위 (0,0)~(n-1,m-1)
			for (int y = 0; y + size <= m; y++) { //ㄷ의 크기는 3k x 3k
				int price = 0; //색을 다시 칠하는 비용
				int lessBlackCnt = blackCnt; //모눈종이의 모든 검은칸의 갯수 - 3k x 3k공간에서 확인된 검은칸의갯수.
											 //즉 남은 검은색갯수
				//1. 3k x 3k칸을 모두 검은색으로 칠하는 비용 계산
				for (int xx = x; xx < x + size; xx++) { //ㄷ내부의 모든 모눈종이를 확인
					for (int yy = y; yy < y + size; yy ++) { //(x,y)~(x+2k,y+2k)확인
						if (map[xx][yy] == -2) { //흰칸을 검은칸으로
							price += a;
						}
						else if (map[xx][yy] == -1) //남은 검은칸의 갯수를 셈
							lessBlackCnt--;
					}
				}
				//2. 3k x 3k이외의 모든 모눈종이칸에있는 검은색을 흰색으로 다시칠해야함
				price += lessBlackCnt * b; 
				
				//3. 흰색칸이어야 하는곳의 비용 계산
				for (int xx = x + k; xx < x + size - k; xx++) {
					for (int yy = y + k; yy < y + size; yy++) {
						if (map[xx][yy] == -2) { //흰칸: 1번에서 필요없는비용을 추가했으니, 다시 빼줌
							price -= a; 
						}
						else if (map[xx][yy] == -1){ //검은칸 : 흰칸으로 칠하는 비용추가
							price += b; 
						}
					}
				}

				//최솟값만 res 에 갱신
				if (res > price)
					res = price; 
			}
		}

	}

	printf("%d", res);
}

void input() {
	scanf("%d%d%d%d", &n, &m, &a, &b);

	map = new int* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[m];
		char _;
		scanf("%c", &_); //줄바꿈문자지움
		for (int j = 0; j < m; j++) {
			scanf("%c", &_);
			if (_ == '#') {
				map[i][j] = -1; //검은칸에는 -1
				blackCnt++; //검은칸 갯수를 셈
			}
			else
				map[i][j] = -2; //흰칸에는 -2
		}
	}

}

int main(void) {
	func();

	return 0;
}