【2014广州市选day1】JZOJ2020年9月12日提高B组T3 消除游戏
2024-10-13 23:44:57
【2014广州市选day1】JZOJ2020年9月12日提高B组T3 消除游戏
题目
Description
相信大家玩过很多网络上的消除类型的游戏,一般来说就是在一个大拼图内找出相同的部分进行最大程度的消除操作。下面我们给出一个拼图以及消除规则,请你找到最大限度的消除方案。
【拼图组成】
拼图为 N行 * M列 的矩阵,每个格子中都放着一个数字,范围是0到9。例如:
4*5 矩阵:
【消除规则】
我们可以从拼图的任意一个格子(坐标【X,Y】)出发,消除该格子的数字,然后,向格子X坐标正负1,Y坐标正负1的范围,寻找和原来格子相同的数字(不能找已经消除过的格子),一并消除,然后在新的格子继续重复上述过程,直到找不到相同的数字为止。这个过程称为消除过程。上面的矩阵中,我们可用以下几种消除方案:
Input
输入第一行为两个整数N (1<=N<=30),M(1<=<=30),用空格隔开下面N行,每行有M个整数(范围0到9)
Output
输出一行为两个整数 X,Y,中间用一个空格隔开,其中X代表消除的数字,Y代表最大的消除数目。
如果一个拼图中有多个数字可以消除相同的最大的数目,那么则输出数字最小的那个解。
Sample Input
4 5
12345
22340
09070
12300
Sample Output
0 5
题目
题意
给出一个由0~9组成的\(n*m\)的矩阵
问最长相同数字链
分析
\(BFS\)不适合,采用\(DFS\)
枚举起点
然后一条路走
走到最后没得走了统计答案
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,ans1,s,a[35][35],d[1005][3],f1[9]={0,-1,-1,-1,0,0,1,1,1},f2[9]={0,-1,0,1,-1,1,-1,0,1};
bool b[35][35];
char str[35];
int read()
{
int res=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();
return res;
}
void dfs(int x,int y,int s)
{
int t=0,xx,yy;
for (int i=1;i<=8;++i)
{
xx=x+f1[i];
yy=y+f2[i];
if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&!b[xx][yy]&&a[xx][yy]==a[x][y])
{
b[xx][yy]=true;
dfs(xx,yy,s+1);
b[xx][yy]=false;
++t;
}
}
if (t==0)
{
if (s>ans||(s==ans&&a[x][y]<ans1))
{
ans=s;
ans1=a[x][y];
}
}
}
int main()
{
freopen("clear.in","r",stdin);
freopen("clear.out","w",stdout);
n=read();m=read();
for (int i=1;i<=n;++i)
{
scanf("%s",str+1);
for (int j=1;j<=m;++j)
a[i][j]=str[j]-'0';
}
ans1=10;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (!b[i][j])
b[i][j]=true,dfs(i,j,1),b[i][j]=false;
printf("%d %d\n",ans1,ans);
fclose(stdin);fclose(stdout);
return 0;
}
最新文章
- 扩展easyUI tab控件,添加加载遮罩效果
- java面试题之ssh
- C#遍历打印机
- Django models通过DateTimeField保存到MySQL的时间的时区问题
- cocos2d-x 2.2.3 之菜单分析(1)
- JAVA三大框架SSH的各自作用
- 从汇编看c++中的虚拟继承及内存布局(二)
- WebForm 内置对象、数据增删改、状态保持
- 手机端仿ios的单级联动脚本三
- 书籍推荐Python编程:从入门到实践(高清完整pdf)
- bzoj4514 数字配对
- 预浸料(Prepreg,PreimpregnatedMaterials)
- Tomcat服务器配置https双向认证(使用keytool生成证书)
- jqgrid 选中行触发编辑,切换下一行时验证和异步保存上一行数据
- &#39;AndroidManifest.xml&#39; must have a minimum of 2 segments.
- shell脚本中对简单实现对log的处理
- [LeetCode] 243. Shortest Word Distance_Easy
- Ubuntu 18.10 安装PDF阅读器
- c语言数字图像处理(四):灰度变换
- CentOS ext4 磁盘分区 格式化 挂载