洛谷P1331 海战 题解

题目链接P1331 海战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

解题思路：

若一个2 * 2正方形中存在3个#则说明他们存在相邻无解

否则说明有解，直接搜即可

#include 
#include 
 
using namespace std;
 
const int N = 1010;
 
int n, m;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
void dfs(int x, int y)
{
    st[x][y] = true;
    
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;
        if (g[a][b] == '.') continue;
        
        dfs(a, b);
    }
}
 
bool check(int x, int y)
{
    int sum = 0;
    if (g[x][y] == '#') sum ++ ;
    if (g[x + 1][y] == '#') sum ++ ;
    if (g[x][y + 1] == '#') sum ++ ;
    if (g[x + 1][y + 1] == '#') sum ++ ;
    
    if (sum == 3) return true; 
    
    return false;
}
 
int main()
{
    cin >> n >> m;
    
    for (int i = 0; i < n; i ++ ) cin >> g[i];
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (i < n - 1 && j < m - 1 && check(i, j)) 
            {
                printf("Bad placement.");
                return 0;
            }
    
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (!st[i][j] && g[i][j] == '#')
            {
                cnt ++ ;
                dfs(i, j);
            }
    
    printf("There are %d ships.", cnt);
    
    return 0;
}