当前位置:编程学习 > C/C++ >>

UVA 12529 Fix the Pond(bfs)

题目大意:

                 给定2N *(2N+1)的地图,地图上有一些可以旋转的门,至少要旋转多少个门,使得可以从(1,1)经过

          所有的点最后到(1,2N+1)。


题解:

                 因为门是稀疏的,只有同奇同偶会有门,可以看出每个阻挡的门的旋转不会在封闭新的块。所以每个块之间

         只要旋转一个门就可以联通了。最后就是求区域个数。

 


 

#include <iostream>   
#include<stdio.h>   
#include<memory.h>   
#include<vector>   
#include<memory.h>   
#include<map>   
using namespace std;  
#define N 650   
struct Node {  
    int x, y;  
} q[600100];  
int g[N][N][5], use[N][N];  
int cnt;  
char ch;  
int i, j, n;  
void BFS(int X, int Y, int c) {  
    use[X][Y] = c;  
    int st, ed, x, y;  
    st = 0;  
    ed = 1;  
    q[1].x = X;  
    q[1].y = Y;  
    while (st < ed) {  
        st++;  
        x = q[st].x;  
        y = q[st].y;  
        if (x - 1 >= 1) {  
            if (!use[x - 1][y] && g[x][y][0] == 1) {  
                ed++;  
                q[ed].x = x - 1;  
                q[ed].y = y;  
                use[x - 1][y] = c;  
            }  
        }  
        if (x + 1 <= 2 * n) {  
            if (!use[x + 1][y] && g[x][y][2] == 1) {  
                ed++;  
                q[ed].x = x + 1;  
                q[ed].y = y;  
                use[x + 1][y] = c;  
            }  
        }  
        if (y - 1 >= 1) {  
            if (!use[x][y - 1] && g[x][y][3] == 1) {  
                ed++;  
                q[ed].x = x;  
                q[ed].y = y - 1;  
                use[x][y - 1] = c;  
            }  
        }  
        if (y + 1 <= 2 * n + 1) {  
            if (!use[x][y + 1] && g[x][y][1] == 1) {  
                ed++;  
                q[ed].x = x;  
                q[ed].y = y + 1;  
                use[x][y + 1] = c;  
            }  
        }  
    }  
}  
char s[N];  
int main() {  
    while (scanf("%d", &n) != EOF) {  
        memset(use, 0, sizeof(use));  
        for (i = 1; i <= 2 * n; i++)  
            for (j = 1; j <= 2 * n + 1; j++)  
                g[i][j][0] = g[i][j][1] = g[i][j][2] = g[i][j][3] = 1;  
        for (i = 1; i < 2 * n; i++) {  
            scanf("%s", s);  
            int k = 0;  
            for (j = 1; j < 2 * n + 1; j++) {  
                if (((i & 1) && (j & 1)) || ((i & 1) == 0 && (j & 1) == 0)) {  
                    ch = s[k++];  
                    if (ch == 'V') {  
                        g[i][j][1] = 0;  
                        g[i][j + 1][3] = 0;  
                        g[i + 1][j][1] = 0;  
                        g[i + 1][j + 1][3] = 0;  
                    } else {  
                        g[i][j][2] = 0;  
                        g[i][j + 1][2] = 0;  
                        g[i + 1][j][0] = 0;  
                        g[i + 1][j + 1][0] = 0;  
                    }  
                }  
            }  
        }  
        cnt = 0;  
        for (i = 1; i <= 2 * n; i++)  
            for (j = 1; j <= 2 * n + 1; j++)  
                if (use[i][j] == 0) {  
                    ++cnt;  
                    BFS(i, j, cnt);  
                }  
  
        printf("%d\n", cnt - 1);  
    }  
    return 0;  
}  

 

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,