hiho #1474 拆字游戏(dfs,记录状态)
2024-10-07 02:27:59
#1474 : 拆字游戏
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Kui喜欢把别人的名字拆开来,比如“螺”就可以拆成“虫田糸”,小Kui的语文学的不是很好,于是她决定使用编程的方式来解决这个问题。
给出一个01矩阵,1占据的部分即为需要拆的字,如果两个1分享一条边,那么它们连通。连通具有传递性,即如果a、b连通,b、c连通,则a、c连通。
连通的一系列1被看做可以拆出的一块,现在小Kui需要输出这些拆出的块(用一个01矩阵表示,并且要求矩阵的大小尽可能的小)。
为了确保输出的顺序尽可能的和书写的顺序一致,小Kui从每个块中选出最左上角的点(最左侧的点中,最靠上的)作为代表点,然后按照代表点从左到右(若相同则按从上到下)的顺序输出所有拆出的块。
输入
输入的第一行为两个正整数N、M,表示01矩阵的大小。
接下来N行,每行M个01字符,描述一个需要拆的字。
对于40%的数据,满足1<=N,M<=10。
对于100%的数据,满足1<=N,M<=500。
输出
按照代表点从左到右(若相同则按从上到下)的顺序输出所有拆出的块。
对于每个块,先输出其大小,然后用对应的01矩阵表示这个块。
额外的样例
样例输入 | 样例输出 |
11 17 00000000000000000 00001111111100000 00000000000000000 00111111111111100 00000000100000000 00000010101110000 00000110100011000 00011100100001000 00000010100000000 00000001100000000 00000000000000000 |
7 13 1111111111111 0000001000000 0000001000000 0000001000000 0000001000000 0000001000000 0000011000000 3 4 0001 0011 1110 1 8 11111111 1 1 1 3 4 1110 0011 0001 |
- 样例输入
-
14 22
0000000000001111111100
0000000000001101101100
0000110000001111111100
0000110000001101101100
0111111110001111111100
0110110110000000000000
0110110110000011000000
0111111110001111111000
0000110000000001100000
0000110110001111111100
0111111111000111111000
0000000010001101101100
0000000000000001100000
0000000000000011100000 - 样例输出
-
10 9
000110000
000110000
111111110
110110110
110110110
111111110
000110000
000110110
111111111
000000010
5 8
11111111
11011011
11111111
11011011
11111111
8 8
00110000
11111110
00011000
11111111
01111110
11011011
00011000
00111000
思路:
本质上是一个深搜的题,不过需要记录深搜的状态,将搜到所有的非联通路径记录下来。
因为是按列的顺序,所以搜的时候优先列方向遍历。
AC代码:
//
// Created by SeeKHit on 2017/3/5.
// #include "iostream"
#include "vector"
#include "algorithm"
#define MAX 505
using namespace std; char a[MAX][MAX];
int di[]={,-,,};
int dj[]={,,,-};
int n,m;
int n1=; //记录多少个块 vector<pair<int,int>> vv[*];//记录图形点的数组 void dfs(int i,int j,int id)
{
a[i][j]='x';
vv[id].push_back(make_pair(i-,j-));
int ar=;
for(int ii=;ii<;ii++)
{
int ni=di[ii]+i,nj=dj[ii]+j;
if(a[ni][nj]=='')
dfs(ni,nj,id);
}
} int vvv[][]; //记录字块
void Print(int id)
{
int cow=,rol=;
int maxx=,minx=1e9,maxy=,miny=1e9;
for(int t=;t<vv[id].size();t++)
{
maxx=max(maxx,vv[id][t].first);
minx=min(minx,vv[id][t].first);
maxy=max(maxy,vv[id][t].second);
miny=min(miny,vv[id][t].second); int x=vv[id][t].first;
int y=vv[id][t].second; }
rol=maxy-miny+;
cow=maxx-minx+;
cout<<cow<<" "<<rol<<endl; for(int t=;t<vv[id].size();t++)
{
int x=vv[id][t].first;
int y=vv[id][t].second; vvv[x-minx][y-miny]=; } for(int i=;i<cow;i++)
{
for(int j=;j<rol;j++)
{
cout<<vvv[i][j];
vvv[i][j]=; }
cout<<endl;
}
} int main()
{
scanf("%d %d",&n,&m);
for(int i=;i<n;i++)
scanf("%s",a[i+]+); for(int j=;j<=m;j++)
for(int i=;i<=n;i++)
{
if(a[i][j]=='')
{
n1++;
dfs(i,j,n1);
}
} for(int i=;i<=n1;i++)
{
Print(i);
}
}
最新文章
- fail树
- magento的url中 去掉多余的目录层级
- Android Design Principles
- cookie和浏览器
- .net通过获取客户端IP地址反查出用户的计算机名
- 第32条:用EnumSet代替位域
- 教您怎么从spring 官网下载参考文档
- HighCharts 具体使用及API文档说明
- Hibernate学习之hibernate执行顺序
- bash no such file or directory in ubuntu 1404
- JS内置对象-自定义对象
- java网络编程(2)——UDP与TCP
- mysql You can&#39;t specify target table &#39;xxx&#39; for update in FROM clause的解决
- 轻松掌握Redux-Action使用方法
- WEBBASE篇: 第五篇, CSS知识3
- Django 表关系
- BootStrap学习(2)_下拉菜单&;按钮组
- 堆排序获取TopN
- Codeforces Round #428 (Div. 2)
- Python 验证进程之间是空间隔离的