n,m,k,q = map(int,input().split()) S = {} G = [[]]*(k+1+q) dv = [(0,1),(1,0),(0,-1),(-1,0)] for i in range(1,k+1): x,y = map(int,input().split()) S[(x,y)] = i G[i] = [0]*4 for d in range(4): u = S.get((x+dv[d][0],y+dv[d][1]),False) if u: G[u][(d+2)%4] = i G[i][d] = u def getable(v): return v and (v[0]==0 and v[2]==0 or v[1]==0 and v[3]==0) def dfs(v,g): #print(f"dfs({v})") ans = 0 Q = [v] while Q: v = Q.pop() #print(f"v={v}") if not g[v]: continue ans += 1 for d in range(4): u = g[v][d] #print(f"u={u}") if u: g[u][(d+2)%4]=0 if getable(g[u]): Q.append(u) g[v]=False return ans def flood(G): g = [a[:] for a in G] ans = 0 for v in range(1,len(g)): if getable(g[v]): ans += dfs(v,g) return ans #print(S) #print(G) print(flood(G)) for i in range(k+1,k+1+q): x,y = map(int,input().split()) if not (x,y) in S: S[(x,y)] = i G[i] = [0]*4 for d in range(4): u = S.get((x+dv[d][0],y+dv[d][1]),False) if u: G[u][(d+2)%4] = i G[i][d] = u else: v = S[(x,y)] for d in range(4): u = G[v][d] if u: G[u][(d+2)%4] = 0 del S[(x,y)] G[v]=[] #print(G) #print(S) print(flood(G))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | n,m,k,q = map(int,input().split()) S = {} G = [[]]*(k+1+q) dv = [(0,1),(1,0),(0,-1),(-1,0)] for i in range(1,k+1): x,y = map(int,input().split()) S[(x,y)] = i G[i] = [0]*4 for d in range(4): u = S.get((x+dv[d][0],y+dv[d][1]),False) if u: G[u][(d+2)%4] = i G[i][d] = u def getable(v): return v and (v[0]==0 and v[2]==0 or v[1]==0 and v[3]==0) def dfs(v,g): #print(f"dfs({v})") ans = 0 Q = [v] while Q: v = Q.pop() #print(f"v={v}") if not g[v]: continue ans += 1 for d in range(4): u = g[v][d] #print(f"u={u}") if u: g[u][(d+2)%4]=0 if getable(g[u]): Q.append(u) g[v]=False return ans def flood(G): g = [a[:] for a in G] ans = 0 for v in range(1,len(g)): if getable(g[v]): ans += dfs(v,g) return ans #print(S) #print(G) print(flood(G)) for i in range(k+1,k+1+q): x,y = map(int,input().split()) if not (x,y) in S: S[(x,y)] = i G[i] = [0]*4 for d in range(4): u = S.get((x+dv[d][0],y+dv[d][1]),False) if u: G[u][(d+2)%4] = i G[i][d] = u else: v = S[(x,y)] for d in range(4): u = G[v][d] if u: G[u][(d+2)%4] = 0 del S[(x,y)] G[v]=[] #print(G) #print(S) print(flood(G)) |