改代码一直re,请问哪里不对了该怎么优化
查看原帖
改代码一直re,请问哪里不对了该怎么优化
1135682
z18764775490s楼主2024/5/11 12:18
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, res, ans = -1;
char g[1002][1002];
int f[1002 * 1002];
bool vis[1002][1002];
bool rs[1002][1002];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
void dfs(int x, int y)
{
    vis[x][y] = res;//标记
    rs[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int xxx = x + dx[i], yyy = y + dy[i];
        if (xxx >= 1 && xxx <= n && yyy >= 1 && yyy <= m && g[xxx][yyy] == '*' && vis[xxx][yyy] != res) {
            f[res]++;
            vis[xxx][yyy] = res;
        }
    }
    f[res]++;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && vis[xx][yy] != res && g[xx][yy] == '.')
        {
            dfs(xx, yy);
        }
    }
    return;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '#') {
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k], ny = j + dy[k];
                    if (g[nx][ny] == '.')g[nx][ny] = '*';
                }
            }
    //用*代表被粘住的位置:即终点

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (g[i][j] == '.' && !rs[i][j]) {
                res++;
                dfs(i, j);
                ans = max(f[res], ans);
            }
        }
    cout << max(ans, 1) << endl;
    return 0;
}
2024/5/11 12:18
加载中...