?思路

深搜的方式，讓它只遍歷矩形塊，然后在下面的遍歷中判斷是否出現矩形塊交叉，但是很難實現，然后發現可以通過在遍歷過程中判斷是否合法。

參考代碼

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1010;

char g[N][N];
int st[N][N];
int r, c;

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

int dfs(int x, int y){
? ? st[x][y] = 1;
? ? for(int i = 0; i < 4; i ++){
? ? ? ? int nx = x + dx[i], ny = y + dy[i];
? ? ? ? if(nx >= 0 && ny >= 0 && nx < r && ny < c)
? ? ? ? ? ? if(g[nx][ny] == '.')
? ? ? ? ? ? ? ? if(g[x][ny] == '#' && g[nx][y] == '#') return 0;
? ? }
? ??
? ? for(int i = 0; i < 4; i ++){
? ? ? ? int nx = x + dx[i + 4], ny = y + dy[i + 4];
? ? ? ? if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
? ? ? ? if(st[nx][ny] || g[nx][ny] == '.') continue;
? ? ? ? if(!dfs(nx, ny)) return 0;
? ? }
? ??
? ? return 1;
}

int main(){
? ? cin >> r >> c;
? ??
? ? for(int i = 0; i < r; i ++) cin >> g[i];
? ??
? ? int res = 0;
? ??
? ? for(int i = 0; i < r; i ++)
? ? ? ? for(int j = 0; j < c; j ++)
? ? ? ? ? ? if(!st[i][j] && g[i][j] == '#')
? ? ? ? ? ? ? ? if(dfs(i, j)) res ++;
? ? ? ? ? ? ? ? else{
? ? ? ? ? ? ? ? ? ? puts("Bad placement.");
? ? ? ? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? ? }
? ??
? ? printf("There are %d ships.", res);
? ? return 0;
}

?