求助:为什么会TLE,哪里还可以优化
查看原帖
求助:为什么会TLE,哪里还可以优化
99452
BDICOMENOW楼主2022/6/6 18:13
#include <iostream>
#include <cstdio>
#pragma warning(disable:4996) 
using namespace std;

int n,m;
int dir[8][2] = { {1,0}, //↓
                  {1,1}, //↘
                  {0,1}, //→
                  {-1,1},//↗
                  {-1,0},
                  {-1,-1},
                  {0,-1},
                  {1,-1}
};

char mm[105][105];      // 存地图
bool vis[105][105];     // 标记是否访问过
bool flag[105][105];    // 用这个数组来标记每一次扎堆的水坑,方便后面改变地图,
                        // 因为我去过水坑让他变成。


void dfs(int x, int y)
{

    for (int i = 0; i < 8; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tx>=0&&ty>=0&&tx<n&&ty<m&&mm[tx][ty] == 'W'&&!vis[tx][ty]) {
            vis[tx][ty] = true;
            flag[tx][ty] = true;
            dfs(tx, ty);
            vis[tx][ty] = false;
        }
    }
}

// 到达过的水坑标记为旱地
void ChangeGoneMap()
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mm[i][j] == 'W'&&flag[i][j]) {
                mm[i][j] = '.';
            }
        }
    }
}

int main() {
    int ans = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> mm[i];
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mm[i][j]=='W') {
                flag[i][j] = true;
                dfs(i, j);
                ChangeGoneMap();
                ans++;
            }
        }
    }
    cout << ans << endl;


    return 0;//结束程序
}
2022/6/6 18:13
加载中...