点灯(11967)
20214 ワード
1.質問
質問リンク
説明:
農夫のジョンは最近、N*Nの部屋がある巨大な穀倉を新築した.各部屋は(1,1)~(N,N)番号(2≦N≦100)までです.暗闇を恐れた雌牛ベシは、できるだけ多くの部屋に明かりを灯そうとした.
ベッシーは唯一明かりがついている部屋(1,1)から出発した.一部の部屋にはスイッチが入っていて、別の部屋の明かりを消したり開けたりすることができます.例えば、(1、1)部屋のスイッチ(1、2)で部屋の電気を消して開けることができる.ベッシーはライトアップされた部屋に入るしかなく、各部屋で上下左右に隣接する部屋に移動できます.
ベッシーが火をつけることができる部屋の最大個数を求めます.
入力
第1行は、整数としてN(2≦N≦100)およびM(1≦M≦20000)を与える.
次のM行は、4つの整数x、y、a、bを与える.これは,(x,y)部屋で(a,b)部屋の明かりをつけて消すことができることを意味する.1つの部屋には複数のスイッチがあり、1つの調火スイッチも複数あります.
しゅつりょく
ベッシーが電気をつけられる部屋の最大数を出力してください.
2.解答
その他の問題と少し特別な
BFS
題がありますベッシーが行ける部屋を拡大することに焦点を当ててシミュレーションを行いましょう.
3 D検出アレイの作成
#define MAX 101
int isLight[MAX][MAX]; // 불이 켜진 방인지?
int isCanMove[MAX][MAX]; // 갈 수 있는 방인지?
int visit[MAX][MAX]; // 방문했던 방인지?
ベシの移動をシミュレーションし続けます.この場合、上記のように3つのステータス値が必要で、ベッシーが行ける部屋をチェックします.
順番に電気をつけましたか.行けるかどうか.訪問したことがありますか.と入力します.
r
行c
列の部屋に行けるかどうかをチェックするにはisLight[r][c]
isCanMove[r][c]
!visit[r][c]
次の順序でナビゲートします.
2- 1. このとき、電気をつけた部屋にもベッシーが見えるようになったら、その部屋の座標も列に入れます.
もちろん、ベッシーが2番の電気をつけた部屋で歩けるようになったとき、部屋の座標をゴールレバーに置く過程自体
現実世界に入ると一瞬その部屋に移動?やってるような気がしますが、
BFS
を逆転してその部屋に遡る愚かな行為よりも、時間の節約が効果的です.3.完全なコード
#define MAX 101
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;
int isLight[MAX][MAX]; // 불이 켜진 방인지?
int isCanMove[MAX][MAX]; // 갈 수 있는 방인지?
int visit[MAX][MAX]; // 방문했던 방인지?
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> adjList[MAX][MAX]; // 인접 리스트
queue<pair<int, int>> q;
bool isOut(int y, int x) {
return y < 1 || y > N || x < 1 || x > N;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
while (M--) {
int y, x, b, a;
cin >> y >> x >> b >> a;
adjList[y][x].push_back({ b, a });
}
isLight[1][1] = 1;
isCanMove[1][1] = 1;
visit[1][1] = 1;
q.push({ 1, 1 });
int ans = 1;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
// 현재 있는 방을 기준으로 베시가 갈 수 있는 영역을 넓힙니다.
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
isCanMove[ny][nx] = 1;
}
// 현재 있는 방에서 불을 켤 수 있는 모든 방에 불을 킵니다.
for (pair<int, int> c : adjList[y][x]) {
int ny = c.first;
int nx = c.second;
// 불이 켜져있지 않다면
if (!isLight[ny][nx]) {
isLight[ny][nx] = 1; // 불을 키고
ans++; // 정답 변수 증가
}
// 불을 킨 방이 갈 수 있고, 방문하지 않았을 때
if (isCanMove[ny][nx] && !visit[ny][nx]) {
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
// 현재 있는 방에서 인접한 방중에 불이 켜진 방의 좌표를 큐에 넣습니다.
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (isLight[ny][nx] && !visit[ny][nx]) {
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
}
cout << ans;
return 0;
}
実はこの問題は画板で説明したほうがいいです.あとでちゃんとボードを使うと必ず修正してアップします
やりすぎた...でもみんなが理解してくれたと信じています
Reference
この問題について(点灯(11967)), 我々は、より多くの情報をここで見つけました https://velog.io/@front/백준-불켜기-11967テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol