洛谷P1162(自我感觉思路还算巧妙的一道题)
2024-08-22 21:06:08
P1162 填涂颜色
题目描述
由数字0 组成的方阵中,有一任意形状闭合圈,闭合圈由数字1构成,围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如:6X6的方阵(n=6),涂色前和涂色后的方阵如下:
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 1 1 1 1
0 1 1 0 0 1 0 1 1 2 2 1
1 1 0 0 0 1 1 1 2 2 2 1
1 0 0 0 0 1 1 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1
输入输出格式
输入格式:
每组测试数据第一行一个整数:n。其中n(1<=n<=30)
接下来n行,由0和1组成的nXn的方阵。
方阵内只有一个闭合圈,圈内至少有一个0。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式:
已经填好数字2的完整方阵。
输入输出样例
输入样例#1:
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
输出样例#1:
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
说明
1<=n<=30
思路:把map定义的大一圈,以防有这样的数据(第二个测试点):
6
0 0 1 1 1 0
1 1 1 0 1 0
1 0 0 0 0 1
1 1 0 1 1 1
0 1 0 1 0 0
0 1 1 1 0 0
然后就可以避免输出这样的
6
2 2 1 1 1 2
1 1 1 2 1 2
1 2 2 2 2 1
1 1 2 1 1 1
2 1 2 1 2 2
2 1 1 1 2 2
#include<iostream>
#include<cstdio>
using namespace std;
int map[][];
bool visit[][];
int sum,m,n;
void dfs(int x,int y)
{
if(x<||x>n+1||y<||y>1+n||map[x][y] == ||visit[x][y])
return;
//注意这里的判断边界是1+n,n会WA3个点
//因为这样矩阵就会多一圈,再结合数据,相信你能懂
map[x][y]=;
//把在1圈之外的0全部换为3,但是上面的判断条件不能有map[x][y]==3,想想为啥
visit[x][y]=true;//标记为已访问
dfs(x+,y);
dfs(x-,y);
dfs(x,y+);
dfs(x,y-);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
cin>>map[i][j];
/*
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(map[i][j]==0||map[i][j]==3)
dfs(0,0);
*/
for(int i=;i<=n;++i)
{
for(int j=;j<=n;j++)
{
switch(map[i][j])
{
case :
cout<<map[i][j]<<" ";
break;
case ://1圈内的
cout<<"2 ";
break;
case ://1圈外的
cout<<"0 ";
}
}
cout<<endl;
}
return ;
}
最新文章
- 初窥Javascript单元测试,附带掌握一门新技能的学习方式。
- ElasticSearch-5.0安装head插件
- ZH奶酪:Java调用NLPIR汉语分词系统
- lightoj1027
- 微信小程序个人理解
- 结构体 typedef struct hash_cell_struct hash_cell_t;
- 防抖(Debouncing)和节流(Throttling)
- Socket套接字
- NOIP2016提高组初赛(1)
- Linux下实现视频读取(三)---Buffer的准备和数据读取
- 游戏UI框架设计(6): 消息传递中心
- 为ivew的Page组件的跳页增加跳页确定按钮
- Requests+正则表达式抓取猫眼电影TOP100
- IPV4地址分类
- 2.初步认识Angular2
- CreateJs入门必知必会
- win10笔记本实现双屏显示的自如切换
- 一个完成的spring xml配置文件
- google搜索 site:pku.edu.cn inurl:aspx 即可查找所有动态网页 =====html(静态网页) asp(动态) jsp(动态) php(动态) cgi(网络程序) aspx(动态)
- URAL题解一