洛谷—P1331 海战题解

题目链接: P1331 海战

题目大意: 在R*C的矩形块中放置船。如果船的位置合法 计算出船的数目，否则输出“Bad placement.”

题解思路： 这道题的难点在于判断是否有船相邻。 通过自己模拟的数据可以得出结论：

方法一： 如果图是不和法的，一定存在如下结构：

# # . #

或

# # # .

或

# . # #

或

. # # #

即在一个2*2的方格中有三个#就表示船的位置放置有错误。

inline bool isValid(int x, int y) { int sum = 0; if (map[x][y] == 1)sum++; if (map[x+1][y] == 1)sum++; if (map[x][y+1] == 1)sum++; if (map[x+1][y+1] == 1)sum++; if (sum == 3) { return false; } return true; }

方法二： 因为船是一个矩形，所以如果位置没有错误时DFS走过的"#"数量应该等于矩形的面积。问题在于求出矩形的长和宽。我们可以使用循环求出从当前点向右的最大距离和向下的最大距离。

inline int DFS_x(int x, int y) { int kx = 0; for (; map[x][y]; x++) { kx++; } return kx; } inline int DFS_y(int x, int y) { int ky = 0; for (; map[x][y]; y++) { ky++; } return ky; }

代码：

方法一：

#include<iostream> #include<algorithm> using namespace std; const int maxn = 5000; const int dx[] = { 1,0,-1,0 }; const int dy[] = { 0,1,0,-1 }; int vis[maxn][maxn],map[maxn][maxn],R,C,ans; char c; inline int DFS_x(int x, int y) { int kx = 0; for (; map[x][y]; x++) { kx++; } return kx; } inline int DFS_y(int x, int y) { int ky = 0; for (; map[x][y]; y++) { ky++; } return ky; } inline bool isValid(int x, int y) { int sum = 0; if (map[x][y] == 1)sum++; if (map[x+1][y] == 1)sum++; if (map[x][y+1] == 1)sum++; if (map[x+1][y+1] == 1)sum++; if (sum == 3) { return false; } return true; } inline void DFS(int x, int y) { if (vis[x][y] || map[x][y] == 0) { return; } vis[x][y] = 1; for (int i = 0; i < 4; i++) { DFS(x + dx[i], y + dy[i]); } } int main() { cin >> R >> C; for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { cin >> c; if (c == '.') { map[i][j] = 0; } else { map[i][j] = 1; } } } for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { if (!isValid(i, j)) { cout << "Bad placement." << endl; return 0; } } } for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { if (!vis[i][j] && map[i][j] == 1) { DFS(i, j); ans++; } } } cout <<"There are "<< ans <<" ships."<< endl; return 0; }

方法二：

#include<iostream> #include<algorithm> using namespace std; const int maxn = 5000; const int dx[] = { 1,0,-1,0 }; const int dy[] = { 0,1,0,-1 }; int vis[maxn][maxn],map[maxn][maxn],R,C,ans,sum; char c; inline int DFS_x(int x, int y) { int kx = 0; for (; map[x][y]; x++) { kx++; } return kx; } inline int DFS_y(int x, int y) { int ky = 0; for (; map[x][y]; y++) { ky++; } return ky; } inline void DFS(int x, int y) { if (vis[x][y] || map[x][y] == 0) { return; } sum++; vis[x][y] = 1; for (int i = 0; i < 4; i++) { DFS(x + dx[i], y + dy[i]); } } int main() { cin >> R >> C; for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { cin >> c; if (c == '.') { map[i][j] = 0; } else { map[i][j] = 1; } } } for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { if (!vis[i][j] && map[i][j] == 1) { sum=0; DFS(i, j); int x=DFS_x(i, j); int y = DFS_y(i, j); if (x * y != sum) { cout << "Bad placement." << endl; return 0; } ans++; } } } cout <<"There are "<< ans <<" ships."<< endl; return 0; }