C/C++ “流感传染”算法问题

  • Z时代
  • 2024-01-10
  • 分类：IT

clipboard.png
clipboard.png

还没有学过算法，感觉用的方法有些笨。
刚学了函数就用上了。
请大神看看有什么可以改进的地方吗，或者有哪些代码不太规范的地方？

而且 vs2015 好像还不支持 变长数组，所以只能定义常量。
有没有大神教一下怎么定义变长数组。

以下是我的代码

#include<iostream>
#include <iomanip>
using namespace std;
const int N = 5;                //定义宿舍边长
char dorm[N][N];                 //定义一个N*N的全局 二维字符数组
int function(int a)
{
    int count = 0;                                             //用来记录所有宿舍共有多少个感染者
    for (int i = 1; i < a; i++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (dorm[i][j] == '@')                         //找到数组中感染的人“@”。把其上下左右都标为“*”，以避免多算上新患者，避免使新患者周围也被传染。
                {
                    if (i + 1 < N && dorm[i + 1][j] != '#' && dorm[i + 1][j] != '@')   //考虑边界和 空房子的情况
                        dorm[i + 1][j] = '*';
                    if (j + 1 < N && dorm[i][j + 1] != '#' && dorm[i][j + 1] != '@')
                        dorm[i][j + 1] = '*';
                    if (i - 1 >= 0 && dorm[i - 1][j] != '#' && dorm[i - 1][j] != '@')
                        dorm[i - 1][j] = '*';
                    if (j - 1 >= 0 && dorm[i][j - 1] != '#' && dorm[i][j - 1] != '@')
                        dorm[i][j - 1] = '*';
                }
            }
        }
        for (int k = 0; k < N; k++)                    //一次传染完成后，将新传染的“*”赋值为“@”
        {
            for (int h = 0; h < N; h++)
            {
                if (dorm[k][h] == '*')
                    dorm[k][h] = '@';
            }
        }
    }
    for (int i = 0; i < N; i++)                               //统计感染者人数
        for (int j = 0; j < N; j++)
        {
            if (dorm[i][j] == '@')
                count++;
        }
    return count;
}
int main()
{
    cout << "请输入宿舍感染情况矩阵:" << endl;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> dorm[i][j];
    int day;                                      //输入第几天
    cout << "请输入第几天:" << endl;
    cin >> day;
    cout << "此时感染人数:" << function(day) << endl;
    cout << "此时感染情况" << endl;
    for (int i = 0; i < N; i++)                   //输出此时的宿舍感染分布情况
    {
        for (int j = 0; j < N; j++)
            cout << dorm[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

回答：

这个答案仅指出一个对于在线判题而言不规范的地方：这个程序的输入输出太罗嗦了。

  • 在线判题应该单纯的cin输入一堆数据，cout输出所需的结果。

  • cin不应当和原题目要求的输入数据，在格式和顺序上产生任何差异。一点不能多、一点不能少。

  • cout不应当和原题目要求的输出数据，在格式和顺序上产生任何差异。一点不能多、一点不能少。

  • cout不应混入任何调试信息，更不应当混入任何“人性化”的输入提示——裁判机会把你的汉字之类全都当作答案来判错的。

如果你的确需要输出一些额外信息，请善加利用cerr标准错误流。

回答：

可以用位运算。100用2个unsigned long就够了。
unsigned long sick100;//用来表示病人
unsigned long person100;//用来表示有人
每天：
先算sick数组，根据规则上下左右都设置1,
然后跟person进行与操作，排除那些空房子。

回答：

变长数组用stl里的vector

回答：

变长数组是C99的特性，VS2015支持C89/C11和部分C99，不支持变长数组

回答：

N的最大值是一百，你就数组 为
arr101 就行了

回答：

@sanix 对于位运算的方法我没看懂，能否讲的更详细点：

  1. 因为是NxN个房间，unsigned long在32位系统是4字节，不知道怎么容纳下每行100个元素？

  2. 根据规则上下左右都设置1这个如何做？

对于时间效率上我的思路：
用空间换时间，可将新增加的感染的人放入一个集合（初始状态是最初感染的人的坐标），每增加一天，就遍历这个集合中的人，在矩阵中找到可以新感染的人，清空这个集合，把新感染的人加入集合中。直到到达指定天数，或者找不到可以新感染的人为止。同时由一个变量increase记录每次新增加的人数。相对你的三层for循环来说有一定的时间优势。

下面写下大概意思的代码：

const int N = 101;
char dorm[N][N];
int day = 输入的天数;
int  x[N*N+1];//记录该天新增病人x坐标
int  y[N*N+1];//y坐标
读入初始化dorm数组，并在遇到病人时，将其在dorm数组中x、y下标分别存入x、y数组，读入完毕，x中下一个元素置为-1作为标记。如初始时有3个病人，则最后x[3]=-1
....
下面计算天数为day时的感染人数
int count = 0;//记录总感染数
p = 0;//x、y数组的指针
q = N*N;
step = 1;//这里用一点小技巧来节省占用空间。把昨天新感染的人和今天新感染的人放入一个x、y数组，一个从0开始往后放，一个从最后一个元素往前放。当step为1时，表明昨天感染的人是从x/y数组前往后放的。
for(int i = 0; i < day; i++)
{
    int increase = 0;//标记当天新增病人
    while(x[p] != -1) 
    {
        判断dorm[x[p]][y[p]]的四个邻居是否可被感染（不为空房子、不为已感染的人），可感染即加入数组，我这里只写一个：假设dorm[a][b]可被感染，则
        x[q] = a; y[q] = b;
        q += -1*step;
        increase++;
        //4个方向都判断过后
        p += step;
    }
    x[p] = -1;//打个收尾标记
    step = -1*step; p = N*N; q = 0;//换个方向存
    if(increase == 0)
    {
        break;//不会有新病人了，之后的感染人数都不会变化，跳出
    }
    count += increase;
}
输出 count

以上是 C/C++ “流感传染”算法问题 的全部内容， 来源链接： utcz.com/p/191791.html

回到顶部