返回题解分享
讨论 / 题解分享/ 帖子详情

全球变暖(编程题) - 题解

注意!注意!注意!



要加边界判定, 最外面一层有岛屿!!!

#include <iostream>
using namespace std;

const int N = 1010;

int n;
char d[N][N];
bool st[N][N];
int res;
bool flag;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

void dfs(int x, int y)
{
    st[x][y] = true;

    bool ret = true;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && nx >= 1 && ny <= n) // 要判断边界
        {
            if (d[nx][ny] == '.') 
                ret = false;// 如果周围有水的话就表示被淹了
        }
    }

    if (ret)
        flag = true;

    if (d[x - 1][y] == '#' && d[x + 1][y] == '#' && d[x][y - 1] == '#' && d[x][y + 1] == '#')
        flag = true;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && nx >= 1 && ny <= n)
        {
            if (!st[nx][ny] && d[nx][ny] == '#')
                dfs(nx, ny);
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> d[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (!st[i][j] && d[i][j] == '#')
            {
                flag = false;
                dfs(i, j);
                if (!flag)
                    res += 1;
            }
        }

    cout << res << endl;

    system("pause");
    return 0;
}
0 回复 0 转发 1 喜欢 4 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!