详细解答2020winter cs106b Assiment2 + bfs

详细解答2020winter cs106b Assiment2 + bfs

目录

• 前言
• Problem One: Rising Tides
• • 海水漫灌过程模拟
  • bfs模板
  • 过程演示
  • 水流的方向
  • 答案
• Part Two: You Got Hufflepuff!
• 结束

前言

1.这是cs106b的第二个作业，在这个作业中，你要学习使用常见的容器，去解决一些问题。
2.cs106b这门课并不建议使用c++官方的STL容器 ，如vector,queue等，而是要使用斯坦福官方为这堂课专门设置的库中的容器, 如Vector,Grid,HashSet等。在下载好的作业文件中斯坦福库就已经成功导入，不需要额外设置。

下面是斯坦福库官方文档的地址，可以查斯坦福容器的语法
/

3.食用本篇博客的最佳方式是自己先做一遍作业，遇到不懂的问题再来看看。
4. 由于大家在做该作业的时候可能还没有学习数据结构和算法，所以我也会写的详细一点。就是肝会比较痛而已

5. 如果看不懂语法，要善用c++标准库搜索！！

Problem One: Rising Tides

你要写一个程序模拟海平面上升。网格里面的数字表示该区域的高度，如果海水的高度>=该区域的高度,那么该区域就会泡在水中。

海水漫灌过程模拟

假如没有地形限制，那么海水灌的过程如下

图中的数字可以代表每一个格子和水源之间的距离。

这个过程可以表示为

1. 水从来源格子(sources)流动到距离为1的格子
2. 1步骤完成后，水从距离为1的格子流向距离为2的格子
3. 2步骤完成后，水从距离为2的盒子流向距离为3的格子
   …
   直到水流到达格子边界，水流就会停下来
   如果加上地形的限制，那么水流停下来就多了一个条件

不难发现整个过程和网格与sources格子的距离有关，所以我们可以尝试使用bfs(广度优先搜索算法)来解决问题。

bfs模板

来源：acwing y总的模板

//st数组是一个bool数组，false表示该点没有被遍历过，true表示该点被遍历过
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);while (q.size())
{int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (!st[j]){st[j] = true; // 表示点j已经被遍历过q.push(j); }}
}

过程演示

以此类推，直到所有能走的点都被遍历过为止

水流的方向

水可以往上下左右四个方向流，怎么用代码表示呢？

//使用数组来表示下一步的方向
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
//这样我们就可以使用一个for循环来向四个方向移动
//分别表示 上 右 下 左 
for(int i = 0; i<4;i++){pair<int , int > newPosition = nowPosition;newPosition.first += dx[i];newPosition.second += dy[i];
}

答案

理解了上面的过程，这题也就没什么难度了,附上解题代码

Grid<bool> floodedRegionsIn(const Grid<double>& terrain,const Vector<GridLocation>& sources,double height) {/* TODO: Delete this line and the next four lines, and implement this function. */Queue<pair<int,int>> q;int dx[4] = {-1,0,1,0};int dy[4] = {0,1,0,-1};int numRows = terrain.numRows();int numCols = terrain.numCols();Grid<bool> state(numRows,numCols,false);for(GridLocation i : sources){int x = i.row;int y = i.queue({x,y});state[x][y] =true;}while(!q.isEmpty()){pair<int, int > t = q.dequeue();int currentX = t.first;int currentY = t.second;for(int i = 0;i<4;i++){int nextX = currentX + dx[i];int nextY = currentY + dy[i];if(nextX<0 || nextX>=numRows || nextY<0|| nextY>= numCols || state[nextX][nextY] == true){continue;}if(terrain[nextX][nextY]<=height){state[nextX][nextY] = queue({nextX,nextY});}}}return state;
}

Part Two: You Got Hufflepuff!

这个模块是让你写一个回答问题的程序，最后可以得出你的性格。
才不是这种呢

这个好像没什么好说的，具体我在代码里加上注释

void administerQuiz(const HashSet<Question>& questions,int numQuestions,const HashSet<Person>& people)
{HashMap<char, int> numScorce;numScorce.add('A',0);numScorce.add('O',0);numScorce.add('E',0);numScorce.add('C',0);numScorce.add('N',0);HashSet<string> questionSet;//遍历numQuestion个变量//questionSet 用来存放已经问过的问题for(int i = 0 ;i<numQuestions;){                            //随机选问题Question curQuestion =  randomElement(questions);if(!ains(curQuestion.questionText)) //如果没有被计算到{questionSet.add(curQuestion.questionText);i++;int questionScore = askPersonalityQuestion(curQuestion);for(auto c :curQuestion.factors.keys()){numScorce[c]+= curQuestion.factors[c] * questionScore;  //curQuestion下的哈希表，key为c,对应的就是 +-1}}}HashMap<char, double> userNomal = nomalizeScore(numScorce);if(nomalizeScore(numScorce).isEmpty()){displayMessage("Don’t have enough information ""to make a determination of who they’re most similar""to");return;}HashMap<double, string> similartiryMap;for (Person p : people){HashMap<char, double> personNomal = nomalizeScore(p.scores);similartiryMap.add(cosineSimilarity(userNomal, personNomal), p.name);}Vector<double> cosineSimi = similartiryMap.keys();cosineSimi.sort();double similarity = cosineSimi[cosineSimi.size() - 1];string name = similartiryMap[similarity];displayMessage(string("You Got ") + name + "!" + "(Similarity: " + to_string(similarity) + ")");}

结束

这里劝大家不要熬夜，熬夜掉头发，更糟糕的是…