论坛 › 数据结构与算法 › 求助两个C语言题目，最好有注释

Taessica 发表于 2018-12-2 16:53:07

求助两个C语言题目，最好有注释

本帖最后由 Taessica 于 2018-12-3 18:50 编辑

1、毒草的入侵
一份自定义大小的苹坪,其中有三种土地形式,普通草,毒草,石头。第0个星期毒草只有一颗。每个星期,毒草会传到已被毒草占领的格子四面八方的每一个没有石头的格(包括垂直与水平相邻的和对角线上相邻的格)1周之后,这些新占领的格又可以把
毒草传到更多的格里面了。
草地由一个图片表示。"M"表示毒草，”.”表示草,而”*”表示大石头.比如这个x=4y=3的例子
....
..* .
M * * .

如果毒草一开始在左下角(第1排,第1列),那么草地的地图将会以如下态势发展
                ....      ..   ..       M M M .          M M M M         M M M M
                ..* .       M M *.      MM * .          M M* M         M M * M
                M * * .      M* *.      M** .          M **.          M **M
星期数         0                1                  2                  3                     4
毒草会在4星期后占领整片土地。

输入                                                                                           输出
4 3 1 1(土地大小和毒草起始位置)                                              4星期
....
..* .
M * * .




2、最大子树和
一株奇怪的花卉,上面共连有N朵花,共有N+1条枝条将花连在一起,并且未修剪时每
朵花都不是孤立的。每朵花都有一个“美丽指数”,该数越大说明这朵花越漂亮,也有“美
丽指数”为负数的,说明这朵花看着都让人恶心所谓“修剪”,意为去掉其中的一条
枝条,这样一株花就成了两株,扔掉其中一株经过一系列“修剪“之后,还剩下最后一
株花(也可能是一朵)。老师的任务就是:通过一系列“修剪”(也可以什么“修剪”都
不进行),使剩下的那株(那朵)花卉上所有花朵的“美丽指数”之和最大。第一行
第一行输入N朵花
第二行输入每朵花的美丽指数
输出最大美丽指数和

人造人 发表于 2018-12-2 17:46:54

一份自定义大小的苹坪,其中有三种土地形式,普通草,草,石头。第个基期
毒草只有一颗。

人造人 发表于 2018-12-2 17:49:11

第一题我好像看懂了，好像不难

Taessica 发表于 2018-12-2 19:33:27

人造人 发表于 2018-12-2 17:49
第一题我好像看懂了，好像不难

完整的代码能写下来吗

人造人 发表于 2018-12-3 12:26:12

一份自定义大小的苹坪,其中有三种土地形式,普通草,草,石头。

提问题要认真呀

人造人 发表于 2018-12-3 12:37:33

#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <windows.h>

enum {STONE = '*', GRASS = '.', BADLY = 'M'};

const std::vector<std::vector<char>> GenerateMap(size_t width, size_t height)
{
        std::vector<std::vector<char>> v;
        v.resize(height);
        for(auto &i: v)
                i.resize(width);

        std::default_random_engine e((unsigned int)time(nullptr));
        std::uniform_int_distribution<size_t> u(0, 2);
        for(auto h = v.begin(); h != v.end(); ++h)
        {
                for(auto w = h->begin(); w != h->end(); ++w)
                {
                        if(u(e))
                                *w = STONE;
                        else
                                *w = GRASS;
                }
        }
        return v;
}

void PrintMap(const std::vector<std::vector<char>> &map)
{
        for(auto h = map.begin(); h != map.end(); ++h)
        {
                for(auto w = h->begin(); w != h->end(); ++w)
                {
                        std::cout << *w << " ";
                }
                std::cout << std::endl;
        }
}

inline bool ConditionInfection(std::vector<std::vector<char>> &map, int x, int y)
{
        if((y >= 0) && (size_t(y) < map.size()))
                if((x >= 0) && (size_t(x) < map.size()))
                        if((map != STONE) && (map != BADLY))
                        {
                                map = BADLY;
                                return true;
                        }
        return false;
}

bool Infection(std::vector<std::vector<char>> &map)
{
        std::vector<POINT> v;
        for(auto h = map.begin(); h != map.end(); ++h)
        {
                for(auto w = h->begin(); w != h->end(); ++w)
                {
                        if(*w == BADLY)
                                v.push_back({w - h->begin(), h - map.begin()});
                }
        }

        // 下面进行感染
        bool flag = false;
        for(auto &i : v)
        {
                if(ConditionInfection(map, i.x, i.y - 1))        // 上
                        flag = true;

                if(ConditionInfection(map, i.x, i.y + 1))        // 下
                        flag = true;

                if(ConditionInfection(map, i.x - 1, i.y))        // 左
                        flag = true;

                if(ConditionInfection(map, i.x + 1, i.y))        // 右
                        flag = true;

                if(ConditionInfection(map, i.x + 1, i.y + 1))        // 右下角
                        flag = true;

                if(ConditionInfection(map, i.x + 1, i.y - 1))        // 右上角
                        flag = true;

                if(ConditionInfection(map, i.x - 1, i.y + 1))        // 左下角
                        flag = true;

                if(ConditionInfection(map, i.x - 1, i.y - 1))        // 左上角
                        flag = true;
        }
        return flag;
}

int main()
{
        std::vector<std::vector<char>> map = {
                {GRASS, GRASS, GRASS, GRASS},
                {GRASS, GRASS, STONE, GRASS},
                {BADLY, STONE, STONE, GRASS},
        };
       
        PrintMap(map);
        while(Infection(map))
        {
                std::cout << "*****************" << std::endl;
                PrintMap(map);
        }

        return 0;
}


. . . .
. . * .
M * * .
*****************
. . . .
M M * .
M * * .
*****************
M M M .
M M * .
M * * .
*****************
M M M M
M M * M
M * * .
*****************
M M M M
M M * M
M * * M
请按任意键继续. . .

人造人 发表于 2018-12-3 12:44:38

#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <windows.h>

enum {STONE = '*', GRASS = '.', BADLY = 'M'};

const std::vector<std::vector<char>> GenerateMap(size_t width, size_t height)
{
        std::vector<std::vector<char>> v;
        v.resize(height);
        for(auto &i: v)
                i.resize(width);

        std::default_random_engine e((unsigned int)time(nullptr));
        std::uniform_int_distribution<size_t> u(0, 2);
        for(auto h = v.begin(); h != v.end(); ++h)
        {
                for(auto w = h->begin(); w != h->end(); ++w)
                {
                        if(u(e))
                                *w = STONE;
                        else
                                *w = GRASS;
                }
        }
        return v;
}

void PrintMap(const std::vector<std::vector<char>> &map)
{
        for(auto h = map.begin(); h != map.end(); ++h)
        {
                for(auto w = h->begin(); w != h->end(); ++w)
                {
                        std::cout << *w << " ";
                }
                std::cout << std::endl;
        }
}

inline bool ConditionInfection(std::vector<std::vector<char>> &map, int x, int y)
{
        if((y >= 0) && (size_t(y) < map.size()))
                if((x >= 0) && (size_t(x) < map.size()))
                        if((map != STONE) && (map != BADLY))
                        {
                                map = BADLY;
                                return true;
                        }
        return false;
}

bool Infection(std::vector<std::vector<char>> &map)
{
        std::vector<POINT> v;
        for(auto h = map.begin(); h != map.end(); ++h)
        {
                for(auto w = h->begin(); w != h->end(); ++w)
                {
                        if(*w == BADLY)
                                v.push_back({w - h->begin(), h - map.begin()});
                }
        }

        // 下面进行感染
        bool flag = false;
        for(auto &i : v)
        {
                if(ConditionInfection(map, i.x, i.y - 1))        // 上
                        flag = true;

                if(ConditionInfection(map, i.x, i.y + 1))        // 下
                        flag = true;

                if(ConditionInfection(map, i.x - 1, i.y))        // 左
                        flag = true;

                if(ConditionInfection(map, i.x + 1, i.y))        // 右
                        flag = true;

                if(ConditionInfection(map, i.x + 1, i.y + 1))        // 右下角
                        flag = true;

                if(ConditionInfection(map, i.x + 1, i.y - 1))        // 右上角
                        flag = true;

                if(ConditionInfection(map, i.x - 1, i.y + 1))        // 左下角
                        flag = true;

                if(ConditionInfection(map, i.x - 1, i.y - 1))        // 左上角
                        flag = true;
        }
        return flag;
}

int main()
{
        std::cout << "请输入: ";
        size_t width, height, x, y;
        std::cin >> width >> height >> x >> y;

        std::vector<std::vector<char>> map = GenerateMap(width, height);
        map = BADLY;        // 这里就使用 原点在左上角，有什么理由使用左下角的原点？
       
        PrintMap(map);
        while(Infection(map))
        {
                std::cout << "*****************" << std::endl;
                PrintMap(map);
        }

        return 0;
}


请输入: 4 3 1 1
. . * *
* M * *
* . * *
*****************
M M * *
* M * *
* M * *
请按任意键继续. . .

请输入: 4 3 0 0
M * * *
* * . *
* * * *
请按任意键继续. . .

请输入: 4 3 0 0
M * * .
. * * .
. . * .
*****************
M * * .
M * * .
. . * .
*****************
M * * .
M * * .
M M * .
请按任意键继续. . .

人造人 发表于 2018-12-3 12:54:15

本帖最后由 人造人 于 2018-12-3 12:56 编辑

一株奇怪的花卉,上面共连有N朵花,共有N1条枝千将花几连在一起,并且未修剪时每
朵花都不是孤立的。

N1   ？？？
你想说的是 N + 1？？？

千将花几   ？？？ 什么鬼 ？
这里我实在联想不出正确问题，应该能猜出这里是写错字了，应该是吧？

再说一次，问问题要认真，你认真的问问题，别人认真的给你回答，你匆匆忙忙提问，别人也匆匆忙忙回答，这样好吗？

人造人 发表于 2018-12-3 12:59:34

第二题在修正错别字的基础上最好举个例子，像第一题那样

Taessica 发表于 2018-12-3 18:51:51

人造人 发表于 2018-12-3 12:54
一株奇怪的花卉,上面共连有N朵花,共有N1条枝千将花几连在一起,并且未修剪时每
朵花都不是孤立的。



抱歉，我确实是打得有点快，而且没有校对，谢谢你的批评，也谢谢你肯帮忙。

Taessica 发表于 2018-12-3 18:52:44

人造人 发表于 2018-12-3 12:59
第二题在修正错别字的基础上最好举个例子，像第一题那样

谢谢，第二题我已经能做出来了。

查看完整版本: 求助两个C语言题目，最好有注释