Write a C++ program called coin collection.cpp to collect maximum number of coin

Question

Write a C++ program called coin collection.cpp to collect maximum number of coins on an n x m board with inaccessible cells Your program should ask a user for a text filename to read a 2-D array of a sequence of numbers. In the array, 1 indicates that there's a coin on the cell, while 0 means no coin. A cell with the number 2 indicates that the cell is not accessible. Your program should display maximum possible coins and path to collect it. If you have more than one path, you only need to display one. You can assume that the board size is less than or equal to 25 x 25 This is a sample run of the program $ gt+-o coin collection coin collection.cpp $ . /coin collection Enter a file name: ./t1.txt Max coins: 3 Path: (1,1)-> (2,1)-> (2,2) -> (3,2)- (3,3)-> (4,3) -> (4,4) For the sample run, t1.txt has the following context 1 2 01 The first line (= 4 and 4 in the example) indicates the numbers of rows and columns in the file. One blank space is used to delimiter the data. Note that there's no blank space at the end of each line. If your program does not read the file properly, your program will get no credit. In the sample execution, the starting indexes of the path are 1, not 0 This is another sample run $ gtt -o coin_collection coin_collection.cpp $ . /coin collection Enter a file name: ./t2.txt Max coins: 1 Path: (1,1)-> (1,2) -> (1,3)-> (1,4)-> (2,4) For the sample run, t2.txt has the following context

Explanation / Answer

Answer :

#include <iostream>
#include <sstream>
#include <string>
#include <fstream>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int R_MAX = 25;
const int C_MAX = 25;
const int MAX_IN = 250;

int main()
{
ifstream myfile;
string file, line;
int content, row = 0, col = 0;
int collector[R_MAX][C_MAX];
int collectorCount[R_MAX][C_MAX];
string storage[MAX_IN];

cout << "Please enter a file name: ";
cin >> file;

myfile.open("input.txt");
if (myfile.fail())
{
cout << "File does not exist." << endl;
exit(1);
}

// Counts the number of rows and colums and inputs
// the content into the array.
while (getline(myfile, line))
{
istringstream stream(line);
col = 0;
while (stream >> content)
{
collector[row][col] = content;
col++;
}
row++;
}

// Dynamic programming algorithm.
collectorCount[0][0] = collector[0][0];

for (int j = 1; j < col; j++)
{
collectorCount[0][j] = collectorCount[0][j - 1] + collector[0][j];
}

for (int i = 1; i <= row; i++)
{
collectorCount[i][0] = collectorCount[i - 1][0] + collector[i][0];

for (int j = 1; j < col; j++)
{
collectorCount[i][j] = max(collectorCount[i - 1][j], collectorCount[i][j - 1]) + collector[i][j];
}
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
cout << collectorCount[i][j] << " ";
}
cout << endl;
}
cout << "Max coins: " << collectorCount[row - 1][col - 1] << endl;
int row2 = row - 1;
int col2 = col - 1;
int count = 0;

cout << "Path: (1,1)->";
stringstream firstConvert, secondConvert;
string firstResult, secondResult;
firstConvert << row;
firstConvert >> firstResult;
secondConvert << col;
secondConvert >> secondResult;
storage[count] = firstResult + "," + secondResult;
count++;
while (row2 > 0 && col2 > 0)
{
/*if (row2 == 0 && col2 == 0)
{
break;
}*/
if (collectorCount[row2 - 1][col2] > collectorCount[row2][col2 - 1])
{
row2--;
stringstream converter, converter2;
string result, result2;
converter << row2 + 1;
converter >> result;
converter2 << col2 + 1;
converter2 >> result2;
storage[count] = result + "," + result2;
}
else
{
col2--;
stringstream converter, converter2;
string result, result2;
converter << row2 + 1;
converter >> result;
converter2 << col2 + 1;
converter2 >> result2;
storage[count] = result + "," + result2;
}
count++;
}

for (int i = count - 1; i >= 0; i--)
{
cout << "(" << storage[i] << ")";
if (i > 0)
{
cout << "->";
}
}
cout << endl;
myfile.close();

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.