好兄弟们帮我看一眼这个深搜,样例过了但是WA
查看原帖
好兄弟们帮我看一眼这个深搜,样例过了但是WA
843596
Otion楼主2023/1/31 18:34
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 300;
int map[N][N];
bool view[N][N];
int row, col;
int record[N];
int area_size = 0;
int total_count = 0;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// record索引代表面积,值代表个数
void dfs(int row_now, int col_now)
{
    area_size++;
    for (int i = 0; i < 4; i++)
    {
        int row_next = row_now + dx[i];
        int col_next = col_now + dy[i];
        if (row_next < 1 || row_next > row || col_next < 1 || col_next > col)
        {
            continue;
        }
        if (row_next >= 1 && row_next <= row && col_next >= 1 && col_next <= col)
        {
            if (map[row_next][col_next] == 1 && view[row_next][col_next] == false)
            {
                view[row_next][col_next] = true;
                dfs(row_next, col_next);
            }
        }
    }
}
int main()
{
    while (1)
    {
        cin >> row >> col;
        if (row == 0 && col == 0)
        {
            break;
        }
        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; j++)
            {
                scanf("%1d", &map[i][j]);
            }
        }
        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; j++)
            {
                if (map[i][j] == 1 && view[i][j] == false)
                {
                    total_count++;
                    view[i][j] = true;
                    dfs(i, j);
                    record[area_size]++;
                    area_size = 0;
                }
            }
        }
        cout << total_count << endl;
        for (int i = 1; i <= 255; i++)
        {
            if (record[i] != 0)
            {
                cout << i << " " << record[i] << endl;
            }
        }
        memset(map, 0, sizeof(map));
        total_count = 0;
        memset(record, 0, sizeof(record));
    }
    return 0;
}
2023/1/31 18:34
加载中...