题解 – XOJ_S0006_Go

题目链接

提供一种更快的思路。

枚举可能存在气的点，并手动去重。

考虑几种情况：

• 该点存在棋子
• 该点的气由多枚棋子带来
• 该点的气由多枚不同颜色棋子带来

要将相同的点放在一块，可以考虑排序一遍，再遍历一遍，就可以去重了，时间复杂度为 \mathcal O(n\log n)。

再想想如何实现棋子与气的分类。设置flag，棋子分别为1、2，气为3、4，去重非常容易实现，总时间复杂度不变。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MAXN = 1e6 + 10;
int n, m1, m2;
int xt, yt;
struct node{
  int x, y;
  int flag = 0;
}G[MAXN];
inline bool cmp(node a, node b) {
  if(a.x == b.x and a.y == b.y)
    return a.flag < b.flag;
  if(a.x == b.x) return a.y < b.y;
  else return a.x < b.x;
}
//添加任何棋子周围的气，排序一遍可以处理
int tx[] = {0, 1, 0, -1};
int ty[] = {1, 0, -1, 0};
int main()
{
  freopen("A.in", "r", stdin);
  // freopen(".out", "w", stdout);
  scanf("%d%d%d", &n, &m1, &m2);
  int cnt = 1;
  for(int i = 1; i <= m1; i++) {
    scanf("%d%d", &xt, &yt);
    G[cnt].x = xt, G[cnt].y = yt, G[cnt++].flag = 1;
    for(int j = 0; j < 4; j++) {
      if(xt + tx[j] < 1 or yt + ty[j] < 1 or xt + tx[j] > n or yt + ty[j] > n) continue;
      G[cnt].flag = 3;
      G[cnt].x = xt + tx[j];
      G[cnt++].y = yt + ty[j];
    }
  }
  int ans1 = 0;
  for(int i = 1; i <= m2; i++) {
    scanf("%d%d", &xt, &yt);
    G[cnt].x = xt, G[cnt].y = yt, G[cnt++].flag = 2;
    for(int j = 0; j < 4; j++) {
      if(xt + tx[j] < 1 or yt + ty[j] < 1 or xt + tx[j] > n or yt + ty[j] > n) continue;
      G[cnt].flag = 4;
      G[cnt].x = xt + tx[j];
      G[cnt++].y = yt + ty[j];
    }
  }
  sort(G + 1, G + 1 + cnt, cmp);
  int ans2 = 0;
  for(int i = 1; i <= cnt; i++) {

    if(G[i].x == G[i - 1].x and G[i].y == G[i - 1].y and (G[i - 1].flag <= 2)) G[i].flag = G[i - 1].flag;
    if(G[i].flag == 3 and (G[i].x != G[i - 1].x or G[i].y != G[i - 1].y)) ans1++;
    if(G[i].flag == 4 and (G[i].x != G[i - 1].x or G[i].y != G[i - 1].y or G[i].flag != G[i - 1].flag)) ans2++;
    // printf("[%d %d %d] ", G[i].x, G[i].y, G[i].flag);
  }
  printf("%d %d\n", ans1, ans2);
  return 0;
}