#23289模擬温風機こんにちは!c++

15477 ワード

simulation baekjoon algorithm 「三星ソフト」テキストリンク

#23289温風機こんにちは! (コードを参照)
(質問にすべてのコードを参考にしました...本当に難しいです)

🌡️1. Input

{東、西、南、北}の方向を{0,1,2,3}に設定

入力値は、温風機の座標と方向、壁の座標と壁が立ち上がる方向、温度を調べる座標があります
温度を調べる座標はvector<pair<int, int>>です.
暖風機と壁はvector<pair<pair<int, int>, int>>と表示されています

壁のために地図をもう一つ作ります.方向は4種類ある.bool wallMap[][][4]からwallMap[y][x][0]=trueはy,xから東(0)方向に壁があることを意味する.

map[][]と入力し、map[][]=0を生成します.その理由は、温風機と調査が必要な座標を別々に保存し、地図には温風機から放出される温度だけが格納されているからです

const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };

int R, C, K, W;

vector <pair<int, int>> pos;
vector <pair<pair<int, int>, int>> wall, heater;

vector<vector<int>> map;
bool wallMap[MAX][MAX][4];

void input() {
	cin >> R >> C >> K;

	map = vector<vector<int>>(R + 1, vector<int>(C + 1));

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0 && map[i][j] != 5)
				heater.push_back(make_pair(make_pair(i, j), map[i][j]));
			else if (map[i][j] == 5)
				pos.push_back(make_pair(i, j));
			map[i][j] = 0;
		}
	}
	cin >> W;
	for (int i = 0; i < W; i++) {
		int a, b, c; cin >> a >> b >> c;
		wall.push_back(make_pair(make_pair(a, b), c));
	}
	
}

void setting_wall() {
	for (int i = 0; i < W; i++) {
		int y = wall[i].first.first;
		int x = wall[i].first.second;
		int t = wall[i].second;

		/*
		t==0 : (y,x)기준으로 북(3)쪽에 벽
		t==1 : (y,x)기준으로 동(0)쪽에 벽
		*/
		if (t == 0) {
			wallMap[y][x][3] = true;
			wallMap[y - 1][x][2] = true;
		}
		else if (t == 1) {
			wallMap[y][x][0] = true;
			wallMap[y][x + 1][1] = true;
		}
	}
}

🌡️2. Spread

温風機の風が広がる方向

まず、温風機が3方向に拡散する、温風機の方向(東、西、南、北)に従って拡散の座標が変化するので、

と定義する.

const int wdy[4][3] = { {-1,0,1}, {-1,0,1}, {1,1,1}, {-1, - 1, - 1}};
const int wdx[4][3] = { {1,1,1}, {-1,-1,-1}, {-1,0,1}, {-1,0,1} };

2 D配列bool update[][]を作成して、次の重複座標を管理します.

温風機の放熱方式はqueueで管理され、queueには温風機の放熱座標、温度が加わって管理されている

東西南北の方向は0、1、2、3の順で格納されているが、問題では1、2、4、3の順で表示されているので方向を変換する(change dir関数を使用)

void spread(int y, int x, int d) {
	bool update[MAX][MAX] = { false, };

	//처음 온풍기 위치에서 온풍기 방향으로 1칸 이동
    
	d = change_dir(d);
	y += dy[d];
	x += dx[d];

	if (y <= 0 || x <= 0 || y > R || x > C) return;

	// (y,x)좌표, 온도
	queue <pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(y, x), 5));

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int wind = q.front().second;

		q.pop();

		map[y][x] += wind;
		if (wind == 1) continue;

		for (int i = 0; i < 3; i++) {
			int ny = y + wdy[d][i];
			int nx = x + wdx[d][i];

			if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;

			if (update[ny][nx]==false && check_wall(y, x, d, i) == true) {
				update[ny][nx] = true;
				q.push(make_pair(make_pair(ny, nx), wind - 1));
			}
		}
	}
}

void spread_wind() {
	for (int i = 0; i < heater.size(); i++) {
		int y = heater[i].first.first;
		int x = heater[i].first.second;
		int d = heater[i].second;

		spread(y, x, d);
	}
}

ここで,風向きが3方向に伝播すると,アクセスされたか否かだけでなく,壁があるか否かを判断し,風に伝播できるか否かを確認する.
その部分はcheck_wall(y,x,d,i)

1回目の呼び出しで、各座標は次のことを指します.

このセクションでは、問題で指定された次の条件に基づいてコードを記述します.

bool check_wall(int y, int x, int d, int i) {

	// (y,x)에서 현재 방향 d로 벽이 없다면 이동 가능
	if (i == 1) {
		if (wallMap[y][x][d]==false) return true;
	}

	// 0=동, 1=서, 2=남, 3=북
	else if (i == 0) {
		if (d == 0) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][3]==false) return true;
		}
	}
	else if (i == 2) {
		if (d == 0) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][3]==false) return true;
		}
	}
	return false;	
}

🌡️3. Control Temperature

風量を調節する部分がすべての部屋で同時に発生するため、温度変化の重み付け値を格納するためにint tmp[][]が生成される.

すべての格子を隣接する格子と比較して温度を調節し,1つの格子を上,下,左,右の4つの格子と比較することを意味する.

一つの格子を探索するときは、四つの格子を比較しなければならないが、前に比較した格子は除外しなければならない->東と南だけを比較すればいい

void control_temperature() {
	int tmp[MAX][MAX] = { 0, };

	for (int y = 1; y <= R; y++) {
		for (int x = 1; x <= C; x++) {
			for (int i = 0; i < 2; i++) {
				int dir = i==0 ? 0 : 2;

				int ny = y + dy[dir];
				int nx = x + dx[dir];

				if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;
				if (wallMap[y][x][dir]==false) {
					pair<int, int> maxCoord, minCoord;
					if (map[y][x] > map[ny][nx]) {
						maxCoord = { y,x };
						minCoord = { ny, nx };
					}
					else {
						maxCoord = { ny, nx };
						minCoord = { y,x };
					}

					int diff = abs(map[y][x] - map[ny][nx]);
					diff /= 4;
					tmp[maxCoord.first][maxCoord.second] -= diff;
					tmp[minCoord.first][minCoord.second] += diff;
				}
			}
		}
	}
	
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			map[i][j] += tmp[i][j];
}

🌡️4. Decrease Temperatrue

最外室の温度を1度

に下げる

このとき注意が重なる可能性のある部分

void decrease_temperatrue() {
	for (int i = 1; i <= C; i++) {
		if (map[1][i] > 0) map[1][i]--;
		if (map[R][i] > 0) map[R][i]--;
	}
	
	for (int i = 2; i < R; i++) {
		if (map[i][1] > 0) map[i][1]--;
		if (map[i][C] > 0) map[i][C]--;
	}
}

🌡️Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };

const int wdy[4][3] = { {-1,0,1}, {-1,0,1}, {1,1,1}, {-1, - 1, - 1}};
const int wdx[4][3] = { {1,1,1}, {-1,-1,-1}, {-1,0,1}, {-1,0,1} };

const int MAX = 21;

using namespace std;

int R, C, K, W;

vector <pair<int, int>> pos;
vector <pair<pair<int, int>, int>> wall, heater;

vector<vector<int>> map;
bool wallMap[MAX][MAX][4];

void print() {
	printf("\n");
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			printf("%2d ", map[i][j]);
		}
		printf("\n");
	}
}

void input() {
	cin >> R >> C >> K;

	map = vector<vector<int>>(R + 1, vector<int>(C + 1));

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0 && map[i][j] != 5)
				heater.push_back(make_pair(make_pair(i, j), map[i][j]));
			else if (map[i][j] == 5)
				pos.push_back(make_pair(i, j));
			map[i][j] = 0;
		}
	}
	cin >> W;
	for (int i = 0; i < W; i++) {
		int a, b, c; cin >> a >> b >> c;
		wall.push_back(make_pair(make_pair(a, b), c));
	}
	
}

void setting_wall() {
	for (int i = 0; i < W; i++) {
		int y = wall[i].first.first;
		int x = wall[i].first.second;
		int t = wall[i].second;

		/*
		t==0 : (y,x)기준으로 북(3)쪽에 벽
		t==1 : (y,x)기준으로 동(0)쪽에 벽
		*/
		if (t == 0) {
			wallMap[y][x][3] = true;
			wallMap[y - 1][x][2] = true;
		}
		else if (t == 1) {
			wallMap[y][x][0] = true;
			wallMap[y][x + 1][1] = true;
		}
	}
}

bool check_wall(int y, int x, int d, int i) {

	// (y,x)에서 현재 방향 d로 벽이 없다면 이동 가능
	if (i == 1) {
		if (wallMap[y][x][d]==false) return true;
	}

	// 0=동, 1=서, 2=남, 3=북
	else if (i == 0) {
		if (d == 0) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][3]==false) return true;
		}
	}
	else if (i == 2) {
		if (d == 0) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][3]==false) return true;
		}
	}
	return false;	
}

int change_dir(int d) {
	switch (d) {
	case 1: return 0;
	case 2: return 1;
	case 3: return 3;
	case 4: return 2;
	}
}

void spread(int y, int x, int d) {
	bool update[MAX][MAX] = { false, };

	d = change_dir(d);
	y += dy[d];
	x += dx[d];

	if (y <= 0 || x <= 0 || y > R || x > C) return;

	// (y,x)좌표, 온도
	queue <pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(y, x), 5));

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int wind = q.front().second;

		q.pop();

		map[y][x] += wind;
		if (wind == 1) continue;

		for (int i = 0; i < 3; i++) {
			int ny = y + wdy[d][i];
			int nx = x + wdx[d][i];

			if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;

			if (update[ny][nx]==false && check_wall(y, x, d, i) == true) {
				update[ny][nx] = true;
				q.push(make_pair(make_pair(ny, nx), wind - 1));
			}
		}
	}
}

void spread_wind() {
	for (int i = 0; i < heater.size(); i++) {
		int y = heater[i].first.first;
		int x = heater[i].first.second;
		int d = heater[i].second;

		spread(y, x, d);
	}
}

void control_temperature() {
	int tmp[MAX][MAX] = { 0, };

	for (int y = 1; y <= R; y++) {
		for (int x = 1; x <= C; x++) {
			for (int i = 0; i < 2; i++) {
				int dir = i==0 ? 0 : 2;

				int ny = y + dy[dir];
				int nx = x + dx[dir];

				if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;
				if (wallMap[y][x][dir]==false) {
					pair<int, int> maxCoord, minCoord;
					if (map[y][x] > map[ny][nx]) {
						maxCoord = { y,x };
						minCoord = { ny, nx };
					}
					else {
						maxCoord = { ny, nx };
						minCoord = { y,x };
					}

					int diff = abs(map[y][x] - map[ny][nx]);
					diff /= 4;
					tmp[maxCoord.first][maxCoord.second] -= diff;
					tmp[minCoord.first][minCoord.second] += diff;
				}
			}
		}
	}
	
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			map[i][j] += tmp[i][j];
}

void decrease_temperatrue() {
	for (int i = 1; i <= C; i++) {
		if (map[1][i] > 0) map[1][i]--;
		if (map[R][i] > 0) map[R][i]--;
	}
	
	for (int i = 2; i < R; i++) {
		if (map[i][1] > 0) map[i][1]--;
		if (map[i][C] > 0) map[i][C]--;
	}
}

bool check() {
	for (int i = 0; i < pos.size(); i++) {
		int y = pos[i].first;
		int x = pos[i].second;

		if (map[y][x] < K) return false;
	}
	return true;
}

void solution() {
	setting_wall();

	int chocolate = 0;

	while (1) {
		if (chocolate > 100) break;

		spread_wind();

		//print();

		control_temperature();

		//print();

		decrease_temperatrue();

		chocolate++;

		//print();

		if (check()) break;
	}
	cout << chocolate << endl;
}

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

	input();
	solution();

	return 0;
}

Reference

この問題について(#23289模擬温風機こんにちは!c++), 我々は、より多くの情報をここで見つけました https://velog.io/@kimmy/Baekjoon-23289-Simulation온풍기-안녕-c

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

POJ 1811 Prime Test

SVG animate呼吸シンチレーション効果を実現