CF525D Arthur and Walls （搜索）

【题目】

https://www.luogu.com.cn/problem/CF525D

【分析】

当且仅当存在一个2*2矩阵出现以下四种情况时，有“*”需要被更改。

. .     . *   * .      . .
. *     . .   . .      * .
（可以看作是以“*”为中心，每逆时针旋转90°记录一次而形成的）

所以可以枚举每个“*”的位置，判断当前“*”是否出现上述情况。如果出现，则将“*”变为“.”。否则继续判断下一个“*”。

【代码实现】

#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[2020][2020];
int mx[8] = {0, 1, -1, 0, 1, -1, -1, 1};
int my[8] = {1, 0, 0, -1, 1, -1, 1, -1};

bool judg(int x, int y){
    if(x < 1 || x > n) return 0;
    if(y < 1 || y > m) return 0;
    return (a[x][y] == '.');
}

bool check(int i, int j){
    if(judg(i - 1, j) && judg(i, j - 1) && judg(i - 1, j - 1)) return true;
    if(judg(i - 1, j) && judg(i, j + 1) && judg(i - 1, j + 1)) return true;
    if(judg(i + 1, j) && judg(i, j - 1) && judg(i + 1, j - 1)) return true;
    if(judg(i + 1, j) && judg(i, j + 1) && judg(i + 1, j + 1)) return true;
    return false;
}

void dfs(int x, int y){
    for(int i = 0; i < 8; ++ i){
        int nx = x + mx[i];
        int ny = y + my[i];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '*' && check(nx, ny))
            a[nx][ny] = '.', dfs(nx, ny);
    }
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; ++ i)
    {
         for(int j = 1; j <= m; ++ j) 
         {
            cin>>a[i][j];//这块用不了scanf,不知道为啥。
         }
    }
       
    
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
            if(a[i][j] == '*'){
                if(check(i, j)) 
                {
                    a[i][j] = '.';
                    dfs(i, j);
                }
            }   
        }
         
    
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            printf("%c",a[i][j]) ;
        }
        printf("
");
    }
    return 0;
}