CodeForces - 699B One Bomb

题目地址:http://codeforces.com/contest/699/problem/B

题目大意:

  一个矩阵,内容由‘.’和‘*’组成(‘.’ 空,‘*’ 代表墙),墙分布在不同位置,现找出一个位置放置 炸弹,炸弹能炸当前位置的一整行和一整列,如果炸弹的位置可以将所有的墙都炸掉,则输出 “YES” 并输出该位置,如果不存在这样一个位置,这输出“NO”.[炸弹可以放在空地或者墙上]

解题思路:

  1. 对每行每列的墙进行统计,如果该位置为墙,则该行的墙数++同时该列的墙++,统计出所有墙的个数cut.

  2.遍历,扫描位置,如果该位置为墙 则总墙数-1, 所在行的墙数+所在列的墙数=cut 则说明该位置可以放置炸弹且可以炸掉所有的墙,如果不存在这样一个位置则“NO”

Ac code:

 #include<bits/stdc++.h>
using namespace std;
int xx[][];
int r[],c[];
int main()
{
int x,y,i,j;
while(~scanf("%d%d",&x,&y))
{
getchar();
memset(r,,sizeof(r));
memset(c,,sizeof(c));
int cut=;
for(i=; i<=x; i++)
{
for(j=; j<=y; j++)
{
xx[i][j]=getchar();
if(xx[i][j]=='*')
{
cut++;
r[i]++;
c[j]++;
}
}
getchar();
}
int flag=,x1,y1;
for(i=; i<=x; i++)
for(j=; j<=y; j++)
{
int sum=r[i]+c[j];
if(xx[i][j]=='*')sum--;
if(sum==cut)
{
flag=;
x1=i;
y1=j;
break;
}
}
if(flag)
cout<<"YES"<<endl<<x1<<' '<<y1<<endl;
else cout<<"NO"<<endl;
}
return ;
}
上一篇:Adapter 启动时报错——2


下一篇:机器学习(4):BP神经网络原理及其python实现