題目描述

思路

這個題需要讀懂題意，即“什么樣的形式表示兩只船相撞？” ----> 上下相鄰或左右相鄰

 如果圖是不和法的，一定存在如下結構：
# # 
. #
或
# #
# .
或
# .
# #
或
. #
# #

即四個格子里有三個#，一個"."就表示相撞（找出的規律，后續可以用）

（借用一下洛谷題解大佬的圖）
這樣就表示兩個不同的船只
即這個是dfs搜連通塊的變形
數據量1000，還行

代碼

基礎的連通塊
輸出的時候有個。別忘了！

#include<bits/stdc++.h>using namespace std;const int N = 1e3+10;
char g[N][N];  //用字符串存儲
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool st[N][N];  //這個其實也可以不要，直接在原圖上修改
int n, m;
bool check(int x, int y)
{int ans = 0;if(g[x][y] == '#')ans++;if(g[x + 1][y] == '#')ans++;if(g[x][y + 1] == '#')ans++;if(g[x+1][y+1] == '#')ans++;if(ans == 3) //相撞return true;return false;}
void dfs(int x, int y)
{for(int i = 0; i < 4; i++){int xx = x +dx[i], yy = y +dy[i];if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] == '#' && !st[xx][yy]){st[xx][yy] = true;dfs(xx, yy);}}
}
int main()
{cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> g[i][j];}}int res = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(check(i, j)){cout<<"Bad placement."<<endl;return 0;}if(!st[i][j]&&g[i][j] == '#') //沒被搜過{res ++;st[i][j] = true;dfs(i, j);
//				cout<<"ok"<<endl;}}}printf("There are %d ships.\n", res);return 0;
}

總結

難點是如何理解船相撞，多畫畫圖！