跳蚤国王和蛐蛐国王的游戏：最小化替换跳蚤

思路：首先判断蛐蛐国王的希望能否被达成，即判断是否存在至少两只跳蚤不连通。如果不存在两只跳蚤不连通，则输出-1。否则，我们需要最小化被替换的跳蚤的个数。\n\n我们可以使用深度优先搜索（DFS）来判断跳蚤的连通性。具体步骤如下：\n\n1. 创建一个二维数组grid，表示网格。初始化为0，表示跳蚤占据的格子。\n2. 遍历输入的蛐蛐的坐标，将对应的格子置为1，表示蛐蛐占据的格子。\n3. 创建一个二维数组visited，表示跳蚤是否被访问过。初始化为false。\n4. 创建一个变量count，表示被替换的跳蚤的个数，初始化为0。\n5. 遍历网格中的每一个格子，如果该格子为0且未被访问过，则进行DFS搜索。\n - 在DFS搜索中，如果当前格子的上下左右四个格子中有跳蚤（值为0）且未被访问过，则将其设为蛐蛐（值为1），并递归搜索。\n - 搜索结束后，count加1。\n6. 如果count大于等于2，则输出count；否则，输出-1。\n\n时间复杂度分析：遍历网格的时间复杂度为O(n * m)，每次DFS搜索的时间复杂度为O(1)，因此总的时间复杂度为O(n * m)。\n\n代码实现如下：\n\npython\ndef dfs(grid, visited, x, y):\n visited[x][y] = True\n n, m = len(grid), len(grid[0])\n dx = [-1, 1, 0, 0]\n dy = [0, 0, -1, 1]\n \n for i in range(4):\n nx, ny = x + dx[i], y + dy[i]\n if nx >= 0 and nx < n and ny >= 0 and ny < m and not visited[nx][ny] and grid[nx][ny] == 0:\n grid[nx][ny] = 1\n dfs(grid, visited, nx, ny)\n\nT = int(input())\nfor _ in range(T):\n n, m, c = map(int, input().split())\n grid = [[0] * m for _ in range(n)]\n visited = [[False] * m for _ in range(n)]\n count = 0\n \n for _ in range(c):\n x, y = map(int, input().split())\n grid[x-1][y-1] = 1\n \n for i in range(n):\n for j in range(m):\n if grid[i][j] == 0 and not visited[i][j]:\n dfs(grid, visited, i, j)\n count += 1\n \n if count >= 2:\n print(count)\n else:\n print(-1)\n\n\n