海战
题目
-
在峰会期间，武装部队得处于高度戒备。警察将监视每一条大街，军队将保卫建筑物，领空将布满了F-2003飞机。此外，巡洋船只和舰队将被派去保护海岸线。不幸的是因为种种原因，国防海军部仅有很少的几位军官能指挥大型海战。因此，他们考虑培养一些新的海军指挥官，他们选择了“海战”游戏来帮助学习。
-
在这个著名的游戏中，在一个方形的盘上放置了固定数量和形状的船只，每只船却不能碰到其它的船。在这个题中，我们仅考虑船是方形的，所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。
输入
- 输入文件头一行由用空格隔开的两个整数R和C组成，1<=R,C<=1000，这两个数分别表示游戏棋盘的行数和列数。接下来的R行每行包含C个字符，每个字符可以为“#”，也可为“.”，“#”表示船只的一部分，“.”表示水。
输出
- 为每一个段落输出一行解。如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出一段话“There are S ships.”,S表示船只的数量。否则输出“Bad placement.”。
输入样例
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#
输出样例
There are 5 ships.
解题思路
其实这道题就是一道DFS，就找到每个#后，再枚举四个方向来找矩形大#，求多少即可.
写题情况
-
第一次：题目理解错误，以为是#的四边不能有船。。。
-
第二次：以为要最大连着的#，判断船只的碰撞，结果错了。。。
-
第三次：
LY
F
LYF
L
Y
F
大佬提出错误，便知道原来是找方形矩阵的数量. -
LY
F
LYF
L
Y
F
大爷帮我压行（只剩三行），像极了
XJ
Q
XJQ
X
J
Q
巨佬的压行.
如下（建议不要看 (〃‘▽’〃) ）：
#include<cstdio>
#include<iostream>
using namespace std; int n,m,sum,summ,ans,xx,yy,maxx,maxy,minx,miny; bool p[1001][1001]; char a[1001][1001];const int dx[4]={-1,1,0,0};const int dy[4]={0,0,-1,1};void dfs(int x,int y){p[x][y]=true;maxx=max(x,maxx);maxy=max(y,maxy);minx=min(x,minx);miny=min(y,miny);summ++;if(!p[x+dx[0]][y]&&x+dx[0]>0&&x+dx[0]<=n&&a[x+dx[0]][y]=='#'){dfs(x+dx[0],y);p[x+dx[0]][y]=true;}if(!p[x+dx[1]][y]&&x+dx[1]>0&&x+dx[1]<=n&&a[x+dx[1]][y]=='#'){dfs(x+dx[1],y);p[x+dx[1]][y]=true;}if(!p[x][y+dy[2]]&&y+dy[2]>0&&y+dy[2]<=m&&a[x][y+dy[2]]=='#'){dfs(x,y+dy[2]);p[x][y+dy[2]]=true;}if(!p[x][y+dy[3]]&&y+dy[3]>0&&y+dy[3]<=m&&a[x][y+dy[3]]=='#'){dfs(x,y+dy[3]);p[x][y+dy[3]]=true;}}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];for(int i=1;i<=n;++i){for(int j=1;j<=m;++j)if (!p[i][j]&&a[i][j]=='#'){summ=0;maxx=maxy=0;minx=miny=2147483647;dfs(i,j);if (summ==((maxx-minx+1)*(maxy-miny+1)))ans++;else{printf("Bad place ment.");return 0;}}}printf("There are %d ships.",ans);return 0;} `
程序如下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,sum,summ,ans,xx,yy,maxx,maxy,minx,miny;
bool p[1001][1001];
char a[1001][1001];
const int dx[4]={-1,1,0,0};//四个方向
const int dy[4]={0,0,-1,1};//同上
void dfs(int x,int y)
{
p[x][y]=true;
maxx=max(x,maxx);//求边长
maxy=max(y,maxy);//同上
minx=min(x,minx);//同上
miny=min(y,miny);//同上
summ++;//计算#矩形的大小
if(!p[x+dx[0]][y]&&x+dx[0]>0&&x+dx[0]<=n&&a[x+dx[0]][y]=='#')//判断上方是否为#，是就再拓展，知道拓展完这个矩形
{
dfs(x+dx[0],y);
p[x+dx[0]][y]=true;//判断是否拓展过
}
if(!p[x+dx[1]][y]&&x+dx[1]>0&&x+dx[1]<=n&&a[x+dx[1]][y]=='#')//判断下方是否为#，是就再拓展，知道拓展完这个矩形
{
dfs(x+dx[1],y);
p[x+dx[1]][y]=true;//判断是否拓展过
}
if(!p[x][y+dy[2]]&&y+dy[2]>0&&y+dy[2]<=m&&a[x][y+dy[2]]=='#')//判断左方是否为#，是就再拓展，知道拓展完这个矩形
{
dfs(x,y+dy[2]);
p[x][y+dy[2]]=true;//判断是否拓展过
}
if(!p[x][y+dy[3]]&&y+dy[3]>0&&y+dy[3]<=m&&a[x][y+dy[3]]=='#')//判断右方是否为#，是就再拓展，知道拓展完这个矩形
{
dfs(x,y+dy[3]);
p[x][y+dy[3]]=true;//判断是否拓展过
}
}
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];
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
if (!p[i][j]&&a[i][j]=='#')
{
summ=0;
maxx=maxy=0;
minx=miny=2147483647;
dfs(i,j);
if (summ==((maxx-minx+1)*(maxy-miny+1)))//判断是否为方形矩形
ans++;
else
{
printf("Bad placement.");
return 0;
}
}
}
printf("There are %d ships.",ans);
//以下是判断是否为方形矩形的另一种方法（不太完善，但可以参考一下）
// {
// if(a[i][j]=='#')
// {
// p[i][j]=true;
// sum=0;
// xx=yy=0;
// for(int ix=i;ix<=n;++ix)
// {
// if(!p[ix][j]&&a[ix][j]=='#')
// {
// yy++;
// p[ix][j]=true;
// }
// else break;
// }
// for(int jy=j;jy<=m;++jy)
// {
// if(!p[i][jy]&&a[i][jy]=='#')
// {
// xx++;
// p[i][jy]=true;
// }
// else break;
// }
// sum=yy*xx;
// dfs(i,j);
// if(sum!=summ)
// {
// printf("Bad placement.");
// return 0;
// }
// else ans++;
// }
// }
return 0;
}