FZU_2150_(BFS)

FZU 2150

  • 题意:随便两个出发点,用最短时间遍历所有草地,不能遍历所有草地输出-1,可以遍历则输出最短时间,
  • 4层循环枚举所有出发点,更新最短时间,
    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
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    #include <iostream>
    #include <string.h>
    #include <queue>

    using namespace std;

    int next1[4][2] = {0,1,1,0,0,-1,-1,0};
    char grid[11][11];
    bool vis[11][11];
    int n,m;
    int cnt;
    struct node {
        int x,y;
        int step;
        node(){}
        node(int a,int b,int c) {
            x = a; y = b; step = c;
        }
    };

    int bfs(int x1,int y1,int x2,int y2) {
        int ans = 0;
        queue<node> que;
        que.push( node(x1,y1,0) );
        que.push( node(x2,y2,0) );
        vis[x1][y1] = 1;
        vis[x2][y2] = 1;

        while ( !que.empty() ) {
            node cur = que.front();
            que.pop();

            for (int i=0; i<4; i++) {
                int tx = cur.x + next1[i][0];
                int ty = cur.y + next1[i][1];
                if (tx<1 || ty<1 || tx>n || ty>m) continue; // 判断边界
                if (grid[tx][ty] == '.') continue;
                if ( !vis[tx][ty] && grid[tx][ty] == '#' ) {
                    vis[tx][ty] = 1;
                    que.push( node(tx,ty,cur.step+1) );
                    if (cur.step + 1 > ans) ans = cur.step+1;
                }

            }
        }
        // 统计一下是否所有的草地走到了
        for (int i=1; i<=n; i++) 
            for (int j=1; j<=m; j++) 
                if (grid[i][j] == '#' && !vis[i][j] ) 
                    return -1; 
        return ans;
    }


    int main() {
    //	freopen("a.txt","r",stdin);
        int times;
        cin >> times;
        while (times--) {
            memset(grid,0,sizeof grid);
            int ans = 0x3f3f3f3f;
            cin >> n >> m;
            for (int i=1; i<=n; i++) 
                for (int j=1; j<=m; j++) 
                    cin >> grid[i][j];
                
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=m; j++) {
                    // 四层循环枚举 所有的起点,起点可以重复
                    for (int a=1; a<=n; a++) {
                        for (int b=1; b<=m; b++) {
                            if (grid[i][j] == '#' && grid[a][b] == '#') {
                                memset(vis,0,sizeof vis);
                                int k = bfs(i,j,a,b);
                                if (k == -1) continue;
                                else 
                                    if (k < ans) ans = k;
                            }
                        }
                    }

                }
            }
            if (ans == 0x3f3f3f3f)
                printf("Case %d: %d\n",++cnt,-1);
            else 
                printf("Case %d: %d\n",++cnt,ans);
        }

        return 0;
    }
算法
BFS

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！