Puzzle hrlp

[Dee5]

Hello guys, I just want to be truthful with you. This is an assignment I was given and I have no idea of where to start.

It's about a puzzle
Here's the question

Mike loves puzzles. He designed a square grid and connects the top left corner of the grid to the bottom right corner of the grid with a continuous path. To make the puzzle easy to solve the path doesn't contain loops or branches. He also gurantees that there is only a single path connecting the two corners.

He then defines the cost of going through the path is the sum of grids that one passes through minus the number of corners that one changes direction.

The first line of the input should represent the size of the grid.
The following line should represent the grid where by 1 represent a path and 0 represent a wall/ not a path.

Example of input
5
10101
10010
11001
01000
01111

Thus the output will be 6
Whereby the total grid where the path has taken is 9 minus the corners which is three corners.

[poteto]

load map into a grid.

traverse grid, count steps excluding corners, print output.

there are many ways to do it, just tell us where you are stuck at. if you want to challenge yourself, you could use A* and allow paths with branches and loops, it is a lot simpler than you would expect if you find the right tutorial, and useful for video games with AI's. Excluding corners is just checking if the direction is equal or different.

[Dee5]

That is the problem
I have no idea about map in c++
Also I learn through codes and i didn't get the code which resembles this question

[againtry]

Start at the end point and work backwards. Move in the one and only direction available. Count steps and any change in direction and get difference. There you go, solved.

[Dee5]

Seems easy to you bruh I'm not that advnced

[againtry]

Another tip.

Set the current row,col position - just like a cursor. Work out where the next move is to be and go there accounting for step/corner as you go. Check whether the new cursor position once you've moved there is 0,0 in which case, bingo, game over, do the sums and report the results.

[salem c]

> This is an assignment I was given and I have no idea of where to start.
All non-trivial programs begin with pencil and paper.

So begin with drawing

100
100
111

and

100
110
011

These should be simple enough that you can work out the answer just by looking at them.

Figure out what kind of data structure you're likely to want to store things.
Figure out how given a position, you determine whether to go right, or go down.
Figure out what it means to turn a corner.

Really small test cases are sufficient to 'test' your algorithm on by hand without writing any code at all.
But what it will do is give you some confidence that you're heading in the right direction.

The whole point of this is that you can throw away many bad ideas quite quickly, without having to spend days on coding just to find out it will never work.

[Dee5]

Thanks for the advice

[Dee5]

My problem is I don't what does it mean to turn a corner

[Dee5]

So far I've only manage to get the size and the elements of the grid
Also to output the grid

#include<iostream>
using namespace std;
int main ()
{
    int i, j, m, n, x, A[10][10]; 
    cout << "Enter number of row and column : ";//
    cin >> m>>n;
    cout << "Enter elements of grid : ";
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)  
            cin >> A[i][j];
    cout << "Grid: \n ";
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
            cout << A[i][j] << " ";
        cout << "\n ";
    }
    for (i = 0; i < m; i++)
    {
        x = A[i][i];
        A[i][i] = A[i][m - i - 1];
        A[i][m - i - 1] = x;
    }
   
    return 0;
}

[salem c]

OK.
But before you continue, give some of those single letter variables more meaningful names.
This isn't the 1970's, where each character cost you 1¢ in storage costs.

OK, you're standing at the top left corner.
How do you decide whether to move right, or move down?

int pos_row = 0, pos_col = 0;
if ( A[pos_row+?][pos_col+?] == 1 ) cout << "Move right";
if ( A[pos_row+?][pos_col+?] == 1 ) cout << "Move down";

[Dee5]

Sorry sir I don't understand the code u wrote

[salem c]

Well the +? things are a "fill in the blanks" part of the exercise.

[ne555]

    for (i = 0; i < m; i++)
    {
        x = A[i][i];
        A[i][i] = A[i][m - i - 1];
        A[i][m - i - 1] = x;
    }

¿what do you think you are doing there?

> Also I learn through codes and i didn't get the code which resembles this question
flood fill will work
bfs, dfs will also work
¿have you heard the story of euridice-orpheus?

> My problem is I don't what does it mean to turn a corner

dict turn wrote:

the act of changing or reversing the direction of the course;

for example: you are travelling to the right and then go up.

> Figure out how given a position, you determine whether to go right, or go down.
@OP: ¿are those your only choices? ¿can you go left or up?

[lastchance]

Note the specification:

To make the puzzle easy to solve the path doesn't contain loops or branches. He also gurantees[sic] that there is only a single path connecting the two corners.

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

//======================================================================

struct PT
{
   int i, j;
   PT operator    + ( PT b ){ return { i + b.i, j + b.j }; }
   PT operator    - ( PT b ){ return { i - b.i, j - b.j }; }
   bool operator == ( PT b ){ return i == b.i && j == b.j; }
   bool operator != ( PT b ){ return !( *this == b ); }
};
ostream & operator << ( ostream &out, const PT p ){ return out << p.i << ' ' << p.j; }

//======================================================================

int main()
{
   istringstream in( "5    \n"
                     "10101\n"
                     "10010\n"
                     "11001\n"
                     "01000\n"
                     "01111\n" );

   int N;
   in >> N;
   vector<string> grid(N);
   for ( int i = 0; i < N; i++ ) in >> grid[i];

   PT topLeft = { 0, 0 }, bottomRight = { N - 1, N - 1 };
   PT p = topLeft, prev = p;
   int length = 1, corners = 0;

   for ( const string &s : grid ) cout << s << '\n';
   cout << "\nRoute:\n";
   cout << p << '\n';

   while ( p != bottomRight )
   {
      for ( PT step : { PT{ -1, 0 }, PT{ 1, 0 }, PT{ 0, -1 }, PT{ 0, 1 } } )
      {
         PT q = p + step;
         if ( q == prev ) continue;
         int i = q.i, j = q.j;
         if (i >= 0 && i < N && j >= 0 && j < N && grid[i][j] == '1' )
         {
            if ( length > 1 && step != p - prev ) corners++;
            prev = p;
            p = q;
            break;
         }
      }
      cout << p << '\n';
      length++;
   }
   cout << "\nLength = " << length << ", corners = " << corners << '\n';
   cout << "Score = " << length - corners << '\n';
}

10101
10010
11001
01000
01111

Route:
0 0
1 0
2 0
2 1
3 1
4 1
4 2
4 3
4 4

Length = 9, corners = 3
Score = 6

[Dee5]

How can the user be allowed to enter the input

[Dee5]

Like deleting the istringstream

[salem c]

Sure, you just change

   in >> N;
   vector<string> grid(N);
   for ( int i = 0; i < N; i++ ) in >> grid[i];

to

   cin >> N;
   vector<string> grid(N);
   for ( int i = 0; i < N; i++ ) cin >> grid[i];

[Dee5]

The program just need o perform the algorithm of getting the answer
The grid should be inputted by the user.
Thanks in advance

[Dee5]

When I try it like this it gives wrong answer

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

//======================================================================

struct PT
{
   int i, j;
   PT operator    + ( PT b ){ return { i + b.i, j + b.j }; }
   PT operator    - ( PT b ){ return { i - b.i, j - b.j }; }
   bool operator == ( PT b ){ return i == b.i && j == b.j; }
   bool operator != ( PT b ){ return !( *this == b ); }
};
ostream & operator << ( ostream &out, const PT p ){ return out << p.i << ' ' << p.j; }

//======================================================================

int main()
{
  int N;
   cout << "Enter grid:";
   cin >> N;
   vector<string> grid(N);
   for ( int i = 0; i < N; i++ ) cin >> grid[i];

   PT topLeft = { 0, 0 }, bottomRight = { N - 1, N - 1 };
   PT p = topLeft, prev = p;
   int length = 1, corners = 0;

   for ( const string &s : grid ) cout << s << '\n';
   cout << "\nRoute:\n";
   cout << p << '\n';

   while ( p != bottomRight )
   {
      for ( PT step : { PT{ -1, 0 }, PT{ 1, 0 }, PT{ 0, -1 }, PT{ 0, 1 } } )
      {
         PT q = p + step;
         if ( q == prev ) continue;
         int i = q.i, j = q.j;
         if (i >= 0 && i < N && j >= 0 && j < N && grid[i][j] == '1' )
         {
            if ( length > 1 && step != p - prev ) corners++;
            prev = p;
            p = q;
            break;
         }
      }
      cout << p << '\n';
      length++;
   }
   cout << "\nLength = " << length << ", corners = " << corners << '\n';
   cout << "Score = " << length - corners << '\n';
}