洛谷P1331 海战
2024-08-27 14:40:08
海战
题目链接
这还是一道联通块的题,只是需要判断是否存在以下四种情况:
o. .o oo oo
oo oo o. .o
如果存在就是Bad placement.
要注意标记以下,不然会出现多次输出Bad placement.的情况。
AC代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 10010
using namespace std;
char G[MAXN][MAXN];
int vis[MAXN][MAXN];
int cnt;
int color;
struct item
{
int x;
int y;
};
int R,C;
queue<item>q;
void bfs(item t)
{
q.push(t);
vis[t.x][t.y]=color;
while(!q.empty())
{
item r;
r=q.front();
q.pop();
//if(vis[r.x][r.y]!=0) continue;
if(G[r.x+1][r.y]=='#'&&r.x+1<=R&&vis[r.x+1][r.y]==0)
{
vis[r.x+1][r.y]=color;
item t2;
t2.x=r.x+1;
t2.y=r.y;
q.push(t2);
}
if(G[r.x-1][r.y]=='#'&&r.x-1>=1&&vis[r.x-1][r.y]==0)
{
vis[r.x-1][r.y]=color;
item t2;
t2.x=r.x-1;
t2.y=r.y;
q.push(t2);
}
if(G[r.x][r.y+1]=='#'&&r.y+1<=C&&vis[r.x][r.y+1]==0)
{
vis[r.x][r.y+1]=color;
item t2;
t2.x=r.x;
t2.y=r.y+1;
q.push(t2);
}
if(G[r.x][r.y-1]=='#'&&r.y-1>=1&&vis[r.x][r.y-1]==0)
{
vis[r.x][r.y-1]=color;
item t2;
t2.x=r.x;
t2.y=r.y-1;
q.push(t2);
}
}
}
int main()
{
scanf("%d%d",&R,&C);
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
cin>>G[i][j];
}
}
item t;
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
if(G[i][j]=='#')
{
t.x=i;
t.y=j;
if(vis[i][j]==0)
{
cnt++;
color++;
bfs(t);
}
}
}
}
bool sign=0;
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
if(G[i][j]=='#'&&G[i+1][j]=='#'&&!sign&&G[i][j+1]=='#'&&G[i+1][j+1]=='.')
{
printf("Bad placement.");
sign=1;
}
else if(G[i][j]=='#'&&G[i+1][j]=='#'&&!sign&&G[i][j+1]=='.'&&G[i+1][j+1]=='#')
{
printf("Bad placement.");
sign=1;
}
else if(G[i][j]=='#'&&G[i+1][j]=='.'&&!sign&&G[i][j+1]=='#'&&G[i+1][j+1]=='#')
{
printf("Bad placement.");
sign=1;
}
else if(G[i][j]=='.'&&G[i+1][j]=='#'&&!sign&&G[i][j+1]=='#'&&G[i+1][j+1]=='#')
{
printf("Bad placement.");
sign=1;
}
}
}
// for(int i=1;i<=R;i++)
// {
// for(int j=1;j<=C;j++)
// {
// cout<<G[i][j];
// }
// cout<<endl;;
// }
if(!sign)
{
printf("There are %d ships.",color);
}
// for(int i=1;i<=R;i++)
// {
// for(int j=1;j<=C;j++)
// {
// printf("%d ",vis[i][j]);
// }
// cout<<endl;;
// }
return 0;
}
最新文章
- 代码的坏味道(21)——中间人(Middle Man)
- Asp.Net工作原理
- xp系统打开软件程序总是弹出警告窗口,很烦人对不,怎么办呢?进来看
- [Linux] 学习笔记之安装学习环境(sshd, lrzsz)
- Spring进阶—如何用Java代码实现邮件发送(二)
- IOS之swift第一课基础代码
- 谈谈GUI的配色和字体选择
- 获取文件CRC和MD5
- android Bitmap(将视图转为bitmap对象)
- DAOFactory复用代码
- XML引入以及与html的区别
- 使用 Helm - 每天5分钟玩转 Docker 容器技术(163)
- [原创]iFPGA-Cable FT2232H JTAG &; UART调试器
- linux下查询java进程以及杀掉其进程
- day40数据库之表的相关操作
- EXPERT FOR SQL SERVER诊断系列--索引
- java 格式化
- “SecureCRT遇到一个致命的错误且必须关闭”处理办法
- decode 横竖转换
- 【LOJ】#2551. 「JSOI2018」列队