成都做公司网站,wordpress弹穿登陆,中国产品网网址,陕西省建设建设监理协会网站【蓝桥杯冲冲冲】Invasion of the Milkweed G 蓝桥杯备赛 | 洛谷做题打卡day30 文章目录 蓝桥杯备赛 | 洛谷做题打卡day30[USACO09OCT] Invasion of the Milkweed G题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 题解代码我的一些话 [USACO09OCT] Invasion of the Mi…【蓝桥杯冲冲冲】Invasion of the Milkweed G 蓝桥杯备赛 | 洛谷做题打卡day30 文章目录 蓝桥杯备赛 | 洛谷做题打卡day30[USACO09OCT] Invasion of the Milkweed G题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 题解代码我的一些话 [USACO09OCT] Invasion of the Milkweed G 题目描述 Farmer John has always done his best to keep the pastures full of luscious, delicious healthy grass for the cows. He has lost the battle, though, as the evil milkweed has attained a foothold in the northwest part of his farm. The pasture, as usual, is partitioned into a rectilinear grid of height Y (1 Y 100) and width X (1 X 100) with (1,1) being in the lower left corner (i.e., arranged as a normal X,Y coordinate grid). The milkweed has initially begun growing at square (Mx,My). Each week the milkweed propagates to all non-rocky squares that surround any square it already occupies, as many as eight more squares (both the rectilinear squares and the diagonals). After only one week in those squares, it is ready to move on to more squares. Bessie wants to enjoy all the grass she can before the pastures are taken over by milkweed. She wonders how long it can last. If the milkweed is in square (Mx,My) at time zero, at what time does it complete its invasion of the pasture (which, for the given input data, will always happen)? The pasture is described by a picture with .s for grass and *s for boulders, like this example with X4 and Y3: ....
..*.
.**.If the milkweed started in the lower left corner (row1, column1), then the map would progress like this: .... .... MMM. MMMM MMMM..*. MM*. MM*. MM*M MM*MM**. M**. M**. M**. M**M
week 0 1 2 3 4The milkweed has taken over the entire field after 4 weeks. POINTS: 125 Farmer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿他在植物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。 草地像往常一样被分割成一个高度为Y(1 Y 100), 宽度为X(1 X 100)的直角网格。(1,1)是左下角的格也就是说坐标排布跟一般的X,Y坐标相同。乳草一开始占领了格(Mx,My)。每个星期乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格包括垂直与水平相邻的和对角在线相邻的格。1周之后这些新占领的格又可以把乳草传播到更多的格里面了。 Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能占领整个草地。如果乳草在0时刻处于格(Mx,My)那么会在哪个时刻它们可以完全占领入侵整片草地呢对给定的数据总是会发生。 输入格式
* Line 1: Four space-separated integers: X, Y, Mx, and My
* Lines 2…Y1: Line y1 describes row (Y2-y) of the field with X characters (‘.’ for grass and ‘*’ for a boulder)
输出格式
* Line 1: A single integer that is the week number when the milkweed takes over the last remaining non-boulder square of the pasture.
样例 #1
样例输入 #1
4 3 1 1
....
..*.
.**.样例输出 #1
4题解代码 学会利用新知自己多试试并尝试积攒一些固定解答方案debug以下是题解代码 ~ #includebits/stdc.h
using namespace std;
int f[105][105],tot1,n,m,sx,sy,Time1,sum;
char Map[105][105];
int l[8][2]{{1,0},{0,1},{-1,0},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
int main()
{memset(f,-1,sizeof(f));cinmnsysx;for(int in;i0;i--)for(int j1;jm;j){cinMap[i][j];if(Map[i][j].) sum;}f[sx][sy]0; while(tot!sum){for(int i1;in;i)for(int j1;jm;j){bool flag0;if(f[i][j]0) continue;if(Map[i][j]*) continue;for(int q0;q8;q){int txil[q][0];int tyjl[q][1];if(tx1||txn||ty1||tym) continue;if(Map[tx][ty]*) continue;if(f[tx][ty]!Time-1) continue;f[i][j]Time; flag1;}if(flag) tot;}Time;}coutTimeendl;return 0;
}我的一些话 今天学习动态规划dp属于比较难的部分这题利用记忆化搜索即可快速解决需要多动脑多思考思路还是很好掌握的虽然一次性AC有一定难度需要通盘的考虑和理解以及扎实的数据结构基础才能独立写出AC代码。但无论难易大家都要持续做题保持题感喔一起坚持(o´ωo) 如果有非计算机专业的uu自学的话关于数据结构的网课推荐看b站上青岛大学王卓老师的课讲的很细致有不懂都可以私信我喔 总结来说思路很重要多想想多在草稿纸上画画用测试数据多调试debug后成功编译并运行出正确结果真的会感到很幸福 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识之前的博文我都有写欢迎大家关注我翻阅自取哦~ 不管什么都要坚持吧三天打鱼两天晒网无法形成肌肉记忆和做题思维该思考的时候一定不要懈怠今天就说这么多啦欢迎评论留言一起成长
