点灯(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つのステータス値が必要で、ベッシーが行ける部屋をチェックします.
順番に電気をつけましたか.行けるかどうか.訪問したことがありますか.と入力します.rc列の部屋に行けるかどうかをチェックするには
  • ライトが点灯している必要があります->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;
    }
    実はこの問題は画板で説明したほうがいいです.
    あとでちゃんとボードを使うと必ず修正してアップします
    やりすぎた...でもみんなが理解してくれたと信じています