HDU 1198 - Farm Irrigation (并查集)

题意

给出9种型状的水道,连通的水道只需要一个装置,问最少需要几个装置。

思路

把每个格子编号,然后和左边、上边判断是否联通。用并查集维护。

代码

int interface[][4] = { {1, 0, 1, 0}, {1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 0}, {0, 0, 1, 1}, {1, 0, 1, 1}, {1, 1, 1, 0}, {0, 1, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1} };
 
int idx(char c) { return c-'A'; }
 
int n, m, num[MAXN][MAXN];
char mp[MAXN][MAXN];
 
int Find(int tmp)
{
    return num[tmp/m][tmp%m] = (tmp == num[tmp/m][tmp%m] ? tmp : Find(num[tmp/m][tmp%m]));
}
 
void Union(int a, int b)
{
    int x = Find(a), y = Find(b);
    if (x != y) num[y/m][y%m] = x;
}
 
void Solve(int x, int y)
{
    if (y > 0 && interface[idx(mp[x][y])][2] && interface[idx(mp[x][y-1])][3]) Union(x*m+y, x*m+y-1);
    if (x > 0 && interface[idx(mp[x][y])][0] && interface[idx(mp[x-1][y])][1]) Union(x*m+y, (x-1)*m+y);
}
 
int main()
{
   // ROP;
    while (scanf("%d%d", &n, &m), n != -1)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%s", mp[i]);
            for (int j = 0; j < m; j++) num[i][j] = i*m+j;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) Solve(i, j);
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (num[i][j] == i*m+j) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

Powered by Jekyll and Theme by solid