点灯(11967)

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]

この3つの状態値でしかベッシーの移動を実現できない.
次の順序でナビゲートします.

現在の部屋を基準に、ベッシーが行ける領域を広げます.

現在の部屋では、点火できるすべての部屋に火をつけます.
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;
}

実はこの問題は画板で説明したほうがいいです.
あとでちゃんとボードを使うと必ず修正してアップします
やりすぎた...でもみんなが理解してくれたと信じています