题意:
思路:
存储网格图不可能开数组a[50000][50000],发现n*m<=400000,可以用a[400001]来存储,(i,j)->a[(i-1)*m+j]。
读入数据时记录下每一行每一列的白色格子数量,然后依次遍历所有格子,当前格子所在行列的白色格子数量就是行+列-公共白色格子。然后记录最小值即可。
总结:
一道很容易T的题目。优化:关闭流同步或用scanf,用memset代替for循环来初始化数组(不用memset会T,用了就A),当最小值已经为0时直接跳出循环,输出0即可。
代码:
#include <iostream>
#include <string.h>
using namespace std;
int q,n,m;
int ans;
int xi[50010],yi[50010];
bool a[400001];
int main()
{
ios::sync_with_stdio(false);
cin>>q;
while(q--)
{
cin>>n>>m;
memset(xi,0,sizeof(xi));
memset(yi,0,sizeof(yi));
ans=1e9;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
if(c=='.')
xi[i]++,yi[j]++,a[(i-1)*m+j]=0;
else if(c=='*')
a[(i-1)*m+j]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int num=xi[i]+yi[j];
if(a[(i-1)*m+j]==0)
num--;
if(num<ans)
ans=num;
if(ans==0)
break;
}
if(ans==0)
break;
}
cout<<ans<<endl;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)