1 条题解

  • 1
    @ 2023-7-1 15:41:44

    咳咳,这道题是一道典型的搜索题(比较简单),所以说......我用的是BFS(宽搜) BFS需要用结构体来实现,不像DFS,要用递归。我递归不太好....... 思路:用一个T[n][n]来保存走过的‘W’,一个cnt来记录有几个。 万能库:#include <bits/stdc++.h> 结构体:queueqx; a[n][n]; int dx[8] = {0, 0, -1, 1, -1, 1, -1, 1};

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

    code:(嘿嘿,我只给关键部分,免得old six😄 )

    void Bfs(int x, int y) {
    	qx.push(x);
    	qy.push(y);
    	while (qx.empty() != 1) {
    		for (int i = 0; i < 8; i++) {
    			int nx = qx.front() + dx[i];
    			int ny = qy.front() + dy[i];
    			if (nx >= n || ny >= m || nx < 0 || ny < 0)
    				continue;
    			if (a[nx][ny] == 'W' && t[nx][ny] == 0) {
    				qx.push(nx);
    				qy.push(ny);
    
    			}
    		}
    		t[qx.front()][qy.front()] = 1;
    		qx.pop();
    		qy.pop();
    	}
    	cnt++;
    }
    
    int main() {
    	cin >> n >> m;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			cin >> a[i][j];
    		}
    	}
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (a[i][j] == 'W' && t[i][j] == 0) {
    				Bfs(i, j);
    			}
    		}
    	}
    	cout << cnt;
    	return 0;
    }
    
    • 1

    信息

    ID
    432
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    56
    已通过
    16
    上传者