数组"/>
XJOI 数组
数组-炸弹
题目描述:
一个月黑风高的晚上你接到了一个爆破任务,有一个n∗m的场地,有些地方有墙,假如你在(i,j)位置投放一个炸弹,第i行和第j列的墙都会被炸毁,现在你想知道是否可以只投放一次炸弹就将所有的墙炸掉。保证至少有一面墙。
输入格式:
第一行一个整数T,表示测试数据的组数
每组数据的
第一行,包含两个整数 n,m
接下来n行,每行m个字符,’*’ 表示墙,’.’表示空地。
输出格式:
如果可以一次炸毁所有的墙在第一行输出“YES”,否则输出”NO”
如果可以一次炸毁所有的墙,在第二行输出投放炸弹的位置x,y
如果有多个位置可以炸毁,输出行号最小的,如果还有多个行号一样小的,输出列标号最小的。
样例输入:
2 3 4 .*.. .... .*..3 3 ..* .*. *..
样例输出:
YES 1 2 NO
约定:
1<=n,m<=1000
#include<iostream>
using namespace std;
int t,n,m,sum;
char k;
int x[1010],y[1010],a,b;
bool g[1010][1010],temp;
int main()
{cin>>t;for(int ti=1;ti<=t;ti++){for(int i=1;i<1010;i++)x[i]=0;for(int i=1;i<1010;i++)y[i]=0;for(int i=1;i<1010;i++)for(int j=1;j<1010;j++)g[i][j]=0;temp=sum=0;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>k;if(k=='*'){x[i]++; //炸弹所在的纵行,每有一个+1y[j]++; //炸弹所在的横行,每有一个+1g[i][j]=1;sum++;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(x[i]+y[j]-g[i][j]==sum){a=i;b=j;temp=1;break;}}if(temp) break;}if(temp==0)cout<<"NO"<<endl;else{cout<<"YES"<<endl;cout<<a<<" "<<b<<endl;}}return 0;
}
更多推荐
XJOI 数组
发布评论