codeforces 614 div2 C - Neko's maze game (발상)

http://codeforces.com/contest/1293/problem/C

 

<문제설명>

2*n (n<=1e5) 배열이 주어진다. 각 칸은 장애물 혹은 길이다.

최대 1e5번의 쿼리가 주어진다. 쿼리에선 (y,x)칸의 상태를 반전시켰을 때 (1,1)~(2,n)까지 경로가 있는지 없는지 출력하면 된다. 

 

<풀이>

예를들어 (0,3)과 쌍이 되어 길을 막을 수 있는 칸은 (1,2), (1,3), (1,4)이다. 

 

장애물을 까는 경우엔, blockedpair의 수가 증가할 여지가 있고, 장애물을 없애는 경우엔 blockedpair의 수가 감소할 여지가 있다. 이때, blockedpair의 수가 0인 경우 경로가 존재한다.

 

<코드>

const int MAX = 1e5 + 2;
int n, q;
bool lava[2][MAX];
int main() {
	FAST;
	cin >> n >> q;
	int blockedPair = 0;
	while (q--) {
		int x, y; cin >> x >> y; x--; y--;
		int delta = (lava[x][y] == 0) ? +1 : -1;

		lava[x][y] = !lava[x][y];
		for (int dy = -1; dy <= 1; dy++) {
			if (y + dy < 0 || y + dy >= n) continue;
			if (lava[!x][y + dy] == 1) blockedPair += delta;
		}
		cout << (blockedPair == 0 ? "YES\n": "NO\n");
	}
}

 

<생각>

순수 발상문제인 것 같다.

 

나는 현재 길이 있는경우/없는경우, lava를만드는 경우/땅을만드는 경우로 나눠서 풀려고 했다. 길이 현재 없는 경우에 lava를 만들때 경로 유무를 판단하는 로직을 고민하다가 실패했다.