蓝桥杯 兰顿蚂蚁 (DFS+模拟)

2024-08-27 02:48
文章标签 模拟 蓝桥 dfs 蚂蚁 兰顿

本文主要是介绍蓝桥杯 兰顿蚂蚁 (DFS+模拟),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目描述】

历届试题 兰顿蚂蚁  
时间限制:1.0s   内存限制:256.0MB  
问题描述


  兰顿蚂蚁,是于1986年,由克里斯·兰顿提出来的,属于细胞自动机的一种。

  平面上的正方形格子被填上黑色或白色。在其中一格正方形内有一只“蚂蚁”。
  蚂蚁的头部朝向为:上下左右其中一方。

  蚂蚁的移动规则十分简单:
  若蚂蚁在黑格,右转90度,将该格改为白格,并向前移一格;
  若蚂蚁在白格,左转90度,将该格改为黑格,并向前移一格。

  规则虽然简单,蚂蚁的行为却十分复杂。刚刚开始时留下的路线都会有接近对称,像是会重复,但不论起始状态如何,蚂蚁经过漫长的混乱活动后,会开辟出一条规则的“高速公路”。

  蚂蚁的路线是很难事先预测的。

  你的任务是根据初始状态,用计算机模拟兰顿蚂蚁在第n步行走后所处的位置。
输入格式
输入数据的第一行是 m n 两个整数(3 < m, n < 100),表示正方形格子的行数和列数。
  接下来是 m 行数据。
  每行数据为 n 个被空格分开的数字。0 表示白格,1 表示黑格。

  接下来是一行数据:x y s k, 其中x y为整数,表示蚂蚁所在行号和列号(行号从上到下增长,列号从左到右增长,都是从0开始编号)。s 是一个大写字母,表示蚂蚁头的朝向,我们约定:上下左右分别用:UDLR表示。k 表示蚂蚁走的步数。
输出格式
输出数据为两个空格分开的整数 p q, 分别表示蚂蚁在k步后,所处格子的行号和列号。
样例输入
5 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
2 3 L 5
样例输出
1 3
样例输入
3 3
0 0 0
1 1 1
1 1 1
1 1 U 6
样例输出
0 0

【解题思路】

如此简单的一道模拟题,硬是搞了好几个小时(囧~~做不出来真的不easy啊),思维陷入了僵局,出不来了,开始用的模拟,细节地方没有处理,也调不出来,于是干脆写了个简单的DFS,各位大神路过请直接无视,弱弱的贴上代码:


#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int map[105][105];
int n,m,i,j;
int xx,yy,k;
char s;
int run;
void dfs(int x,int y,char ss)
{if(run==k){printf("%d %d\n",x,y);return;}if(map[x][y]==0){if(s=='U'){s='L';map[x][y]=1;y=y-1;run++;dfs(x,y,s);}else  if(s=='D'){s='R';map[x][y]=1;y=y+1;run++;dfs(x,y,s);}else  if(s=='L'){s='D';map[x][y]=1;x=x+1;run++;dfs(x,y,s);}else if (s=='R'){s='U';map[x][y]=1;x=x-1;run++;dfs(x,y,s);}}else{if(s=='U'){s='R';map[x][y]=0;y=y+1;run++;dfs(x,y,s);}else  if(s=='L'){s='U';map[x][y]=0;x=x-1;run++;dfs(x,y,s);}else  if(s=='D'){s='L';map[x][y]=0;y=y-1;run++;dfs(x,y,s);}else if(s=='R'){s='D';map[x][y]=0;x=x+1;run++;dfs(x,y,s);}}
}
int main()
{cin>>n>>m;for(i=0; i<n; ++i)for(j=0; j<m; ++j){cin>>map[i][j];}run=0;cin>>xx>>yy>>s>>k;dfs(xx,yy,s);return 0;
}




这篇关于蓝桥杯 兰顿蚂蚁 (DFS+模拟)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110417

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访