这个题目是一个评估感染的问题
主要用到STL的Vector和分治法思想及迭代
背景就不管了看一下描述
Description
This assignment asks you to finish the implementation of a program that assesses the level of infection in a tissue sample. You are given data representing a rectangular tissue sample, overlaid with a grid. Certain portions of the tissue are infected; others are not. Your goal is to help assess the extent of the infection by writing a program that, given the coordinates of a colony of infection, can determine its size.
A typical use of the program follows. The user interacts with the program only through command-line arguments. The user supplies to the program a data filename and the coordinates of a cell in the grid. The coordinates are specified by row and then column, both starting at zero. The program calculates the extent of infection at that coordinate and outputs a two-dimensional representation of the tissue sample. Figure 1 depicts the execution of the program.
Figure 1 Output from a sample solution
For the purpose of this assessment, we consider a "colony" of infected tissue to be a set of adjacent and infected cells. In Figure 1, we can see three separate colonies. The smallest colony consists of two cells and is located in the lower left corner of the grid. Another colony consisting of three infected cells exists on the far right edge of the grid. The largest colony of eight cells resides primarily in the middle of the grid. This colony has a small arm into the upper left corner of the grid. Notice from this colony that cells residing in diagonals are considered "adjacent." The plus signs next to the cells in this largest colony indicate that they all belong to the colony that contains the user entered coordinate
我也看不全懂，大体意思应该是：给定一个网格，其实也就是一个二维数组，从文件sample.grid中读入一些坐标位置，在这些坐标就表示已经感染了，然后要求程序计算感染的程度并输出二维数组表示的组织样本，我们看那个样本输出图片可以看到三个独立的块，一组带+号，其余两组没有，最多的八个所在的中间主要在网格。只要和他们相邻的（周围八个都算相邻）都有+号，可以想象如果我们把第三第四个参数改为5 0，那么输出的结果应该是左下角的那两个带有+号，其余的没有，这个就是本题的关键
一共三个文件
- main.cpp - This file contains the main routine. You do not need to modify this file.
- grid.h - This file contains the declaration of class grid.
- grid.cpp - This file contains the implementation of class grid.
sample.grid - A data file containing sample tissue data. This file was used during the creation of the screen shot in Figure 1
然后看题目的做法
- Begin by studying the program and class grid in its original state. Compile and run the program to get a feel for the command-line interface. Use the sample.grid data file. Make sure you understand how the main routine uses class grid, and what the class grid constructor accomplishes. Pay particular attention to how class grid represents the cell data. Even though the tissue sample is a two-dimensional object, a one-dimensional data structure (a vector) is used for representation.
2.Finish the implementation of function grid::count. This routine should use a divide-and-conquer recursive approach to solve the problem. This means you will have two or more recursive calls in function grid::count. To correctly complete function grid::count, you will have to add additional data members and/or functions to class grid. You will also have to alter other existing code. For instance, you will have to alter the overloaded << operator implementation to output a plus sign (+) next to cells that belong to a colony that subsumes the user entered coordinate.
下面给出代码：main.cpp
#include <iostream> #include <string> #include <cstdlib> #include "grid.h" using namespace std; /* * 作者：白强 * 这个main函数比较简单 * 读入文件以及两个参数 * 然后创建grid对象，调用里面的方法并输出结果 * 最后再删除这个对象 * */ int main (int argc, char *argv[]) { //当参数不是四个的时候程序异常退出 if (argc != 4) { cerr << "Usage: " << argv[0] << " grid_file col_no row_no" << endl << endl; return EXIT_FAILURE; } //创建一个grid对象 grid *g; //实例化之 g = new grid (argv[1]); //得到第三第四个参数并且转换为int型 int row = atoi (argv[2]); int col = atoi (argv[3]); //调用grid的函数输出结果 cout << "The colony including the cell at " << "(" << row << "," << col << ")" << " has an area of " << g->count (row, col) << " units." << endl; //注意<<已经被重载 cout << *g << endl; delete g; return EXIT_SUCCESS; }
接下来就是我们的工作了，完成grid.h并实现其中的函数,完成grid.cpp
#ifndef GRID_H #define GRID_H #include <string> #include <vector> using namespace std; /* * 注释：白强 * 下面是对这个类的操作要求 * 我们创建了一个 vector<bool> *marks，没有使用public方法 * 主要有下面的方法用来完成计算 * 得到元素的位置 * int indexof (int row, int col) const; * 判断是否感染 bool infected(int row, int col) const; * 判断是否已经来过 bool visited(int row, int col) const; */ /* * IMPORTANT NOTE: * * For this assignment, you might need to add state to the * class and/or augment existing methods, and/or create helper * methods, but you shold not delare new public methods */ const bool INFECTED = true; const bool NOT_INFECTED = false; class grid; class grid { private: int rows; int cols; //是否来过及是否感染 vector<bool> *area; vector<bool> *marks; int indexof (int row, int col) const; bool infected(int row, int col) const; bool visited(int row, int col) const; public: //构造函数读入文件并提取数据 grid (string file); //析构函数 ~grid (); //计算一共有多少个在一块，例如图片中的是八个在一起都有+号 int count (int row, int col); //重载流操作符<<输入对象 friend ostream &operator<<(ostream &stream, const grid& ob); }; #endif
grid.cpp
#include <iostream> #include <fstream> using namespace std; //对grid类的实现 #include "grid.h" //得到它的位置，总列*当前行数+当前列数 int grid::indexof (int row, int col) const { return row*cols+col; } //判断是否感染，返回一个bool bool grid::infected(int row, int col) const { return ((*area)[indexof(row, col)] == INFECTED); } //判断是否来过，如果多次来过，说明它在参数row和col所在的区域内 bool grid::visited(int row, int col) const { return ((*visit)[indexof(row, col)] == true); } //构造函数，读入文件 grid::grid (string file) { ifstream grid_file; grid_file.open (file.c_str()); //得到总的行数和列数 grid_file >> rows; grid_file >> cols; //两个vector，一个是感染的区域，一个是标记是否已经来过 area = new vector<bool>(rows*cols, NOT_INFECTED); visit = new vector<bool>(rows*cols, false); //无限循环直到文件结尾跳出循环 while (true) { int blob_row; int blob_col; //得到被感染的点的位置 grid_file >> blob_row; grid_file >> blob_col; //文件结尾跳出循环 if (grid_file.eof()) { break; } //指明这些点都已经被感染 area->operator[](indexof(blob_row,blob_col)) = INFECTED; } //关闭文件 grid_file.close(); } //析构函数删除两个vector grid::~grid () { delete area; delete visit; } //输出数组，二次循环 ostream &operator<<(ostream &stream, const grid& ob) { for (int row=0; row < ob.rows; row++) { for (int col=0; col < ob.cols; col++) { stream << ob.area->operator[](ob.indexof(row, col)); //如果多次来过，说明它在参数row和col所在的区域内，添加标记+号和空格 if (ob.visited(row, col)) { stream << "+ "; } //一般情况直接输出空格 else { stream << " "; } } //换行 stream << endl; } stream << endl; return stream; } int grid::count (int row, int col) { //防止越界 if (row < 0 || col < 0 || row >= rows || col >= cols) { return 0; } //如果周围的都没有被感染或者是我们已经来过 if (! infected(row, col) || visited(row, col)) { return 0; } //表示当前这个店我们已经来过了 visit->operator[](indexof(row,col)) = true; //迭代求取周围八个点的感染情况，周围八点在向外扩直到一个点的周围八点都没有被感染就完成迭代 return count (row-1, col-1) + count(row-1, col) + count (row-1, col+1) + count (row, col-1) + 1 + count (row, col+1) + count (row+1, col-1) + count(row+1, col) + count (row+1, col+1); }
Submit only the following.
- grid.h - your updated class grid declaration
grid.cpp - your updated class grid implementation
最后附上sample.grid文件
6 6
0 0
1 1
2 2
2 3
2 5
3 2
3 3
3 5
4 0
4 2
4 3
4 5
5 0