题意:
从给定的图中找出某些点,这些点能够消除同一行和同一列的“怪物”。求使得最少的点的位置。
关键:要想消除整张的图的妖怪,必须选中n个点(对于n行n列来说)!!!!!!!!!!!
做法:对于每一行来说都要被消去,则每一行都至少要有一个 ‘ . ’;另外就是如果这种方法不行,则看每一列。
如果每一列都有一个 ' . ',同样也是可行的。
#include<stdio.h>
#include<string.h>
const int maxn = 105;
char mat[ maxn ][ maxn ];
bool vis[ maxn ][ maxn ];
struct node{
int x,y;
}ans[ maxn<<2 ];
bool judge( int n ){
for( int i=1;i<=n;i++ ){
for( int j=1;j<=n;j++ ){
if( vis[i][j]==false )
return false;
}
}
return true;
}
int main(){
int n;
while( scanf("%d",&n)==1 ){
for( int i=1;i<=n;i++ ){
scanf("%s",mat[i]+1);
}
memset( vis,false,sizeof( vis ) );
int cnt = 0;
for( int i=1;i<=n;i++ ){
int fy = -1;
for( int j=1;j<=n;j++ ){
if( mat[i][j]=='.' ){
fy = j;
break;
}
}
if( fy==-1 )
continue;
for( int k=1;k<=n;k++ ){
vis[ i ][ k ] = true;
vis[ k ][ fy ] = true;
}
ans[cnt].x = i;
ans[cnt].y = fy;
cnt++;
}//each row need one '.'
if( judge(n)==true ){
for( int i=0;i<cnt;i++ )
printf("%d %d\n",ans[i].x,ans[i].y);
continue;
}
cnt = 0;
memset( vis,false,sizeof( vis ) );
for( int i=1;i<=n;i++ ){
int fx = -1;
for( int j=1;j<=n;j++ ){
if( mat[j][i]=='.' ){
fx = j;
break;
}
}
if( fx==-1 )
continue;
for( int k=1;k<=n;k++ ){
vis[k][i] = true;
vis[fx][k] = true;
}
ans[cnt].x = fx;
ans[cnt].y = i;
cnt++;
}
if( judge(n)==true ){
for( int i=0;i<cnt;i++ )
printf("%d %d\n",ans[i].x,ans[i].y);
continue;
}
printf("-1\n");
}
return 0;
}
分享到:
相关推荐
linux
银行秒杀系统 第十三服创比赛项目
单页登录源码 login登录页源码 html源码
理性力学 陈至达.pdf
JAVA在线考试管理系统(源代码+论文+开题报告+外文翻译+英文文献+答辩PPT)
加州房价预测是一个经典的机器学习案例,旨在通过给定的一些特征来预测加州地区房屋的中位数价格。这个案例通常使用监督学习算法来解决: 其中包括以下步骤: 数据收集:收集加州地区的房屋数据,包括房屋的各种特征,如房屋的位置、面积、卧室数量、人口密度等。 数据预处理:对收集到的数据进行清洗和处理,包括处理缺失值、异常值和重复值,进行特征选择和特征缩放等。 特征工程:根据问题的背景和数据的特点,进行特征工程,提取更有意义和相关性的特征。例如,可以通过计算每个区域的人均收入、房屋间距离海洋的距离等特征。 模型选择:选择适合解决这个问题的机器学习模型。常用的模型包括线性回归、决策树、支持向量机、神经网络等。 模型训练:使用训练数据对选定的模型进行训练,通过调整模型参数来最小化预测误差。 模型评估:使用测试数据对训练好的模型进行评估,常用的评估指标包括均方误差和决定系数等。 模型优化:根据评估结果,对模型进行优化,可以尝试调整模型参数、增加更多的特征、尝试其他算法等。 模型应用:使用优化后的模型进行加州房价的预测,可以输入新的特征数据,得到预测的房价。
web单页html主页老款 旧风格 管理页源码
旅游大数据HTML模板源码 大数据大屏展示源码 VUE
moood UI KitAdobeXD源码下载设计素材UI设计
生物信息学课程学习笔记第四版2022版
在校时,参加的创新创业比赛的项目,我负责前端Vue模块
AProject_Inner_Responsive_TemplatesAdobeXD源码下载设计素材UI设计
基于STM32的智能台灯 项目概述 该智能台灯能够实时监测环境光照强度,并根据环境亮度调整LED灯的亮度,亦可通过面板对台灯进行手动控制,从而实现智能护眼和节能的目的。 功能描述 1.环境感知功能:实时监测环境光照强度 2.信息显示功能:显示亮度等提示信息 3.面板控制功能:模式和光照等级切换 4.远程控制功能:远程开关LED灯 中断级调度任务 1.面板控制任务 2.环境感知任务 3.远程控制任务
HTML4-Desktop-App模板官网落地页APP主页产品宣传页源码 landing静态页面
自己学习机器学习算法过程中写的一些代码,由于换了个方向,暂时没法继续手写实现下去了。
名称 范围 默认参数 系统 ①低功耗系统 ②非低功耗系统 ① 功耗 不广播状态 1uA 广播状态200ms 0.14mA 广播配置 广播间隔时间: 间隔广播(20ms-2000ms) 200ms 广播数据: 设备名称 “Sensor” 制造商数据: FF 前两字节公司ID FFC1 A数据(uint16_t) 1001 B数据(uint16_t) 2001 C数据(uint16_t) 3001 D数据(uint16_t) 4001 E数据(uint16_t) 5001 F数据(uint16_t) 6001 G数据(uint16_t) 7001
因为在我们刷题的过程中,一定可以刷到一些难度很高却十分简单的题,俗话说就是“占着毛肯不拉屎”的水题,下面我就分享几个,因为虽然简单,但难度标准高,所以可以增加等级,刷题量,排名。那是多好的事啊,所以如果你有oj账号,那直接去用。没有没关系,你可以注册一个oj账号,那还等什么,赶紧行动吧!!!!!!!!!
AEM-CoreComponents-UI-KitAdobeXD源码下载设计素材UI设计
电子密码锁使用说明(1).doc
c++语言学生成绩管理文字版.zip;c++语言学生成绩管理文字版.zip;c++语言学生成绩管理文字版.zip