Backtrack problem count the square

Question

0.00/5 (No votes)

See more:

I want to count All the square and rectangle between the coordinates by the backtracking Algorithm and I need help to complete my code to Do that
The Table will be Like :
if I Enter the points (1,1),(1,2),(2,1),(2,2),(3,1),(3,2),(5,2),(3,3)..

___1 2 3 4 5 6 7  
1  * * * 0 0 0 0 
2  * * * 0 * 0 0 
3  * * * 0 0 0 0

Here supposed to be : the count of the squares=2 "the first is formed by the points (1,1)&(1,2)&(2,1)&(2,2), the second by (1,1)&(3,1)&(1,3)&(3,3) "
and Rectangle=1 "it is (1,1)&(3,1)&(1,2)&(3,2)

What I have tried:

C++

#include <iostream>
#include <iomanip>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

const size_t size=20;

char table[size][size];

void table_clear(void){
    for(int v = 0; v<size; ++v)
        for(int h = 0; h<size; ++h)
            table[v][h]=' ';
}

void table_put(pair<int, int> p){
    int v = p.first;
    int h = p.second;
    table[v-1][h-1] = '*';//to zero origin
}

void table_disp(){
    cout << "***";
    for(int i=0; i<size;++i){
        cout << setw(3) << i + 1;
    }
    cout << "\n" << endl;
    for(int i=0;i<size;++i,cout<<endl){
        cout << setw(3) << left << i + 1;
        for(int j=0;j<size;++j){
            cout << setw(3) << right << table[i][j];
        }
        cout<<endl;
    }
}

int main(){
    vector<pair<int,int> > v;
    pair<int, int> end(99,99);
    pair<int, int> XY;

    cout << "Enter each cell in first colony use row space column Enter format, 3 4, for example.\n";
    cout << "Enter 99 99 to end entries." << endl;

while(1){
        int x,y;
        cin >> y;
        cin >> x;
        XY = make_pair(x,y);
        if(XY == end)
            break;
        v.push_back(XY);
    }
    cout<<"\n\n";

    table_clear();
    for(vector<pair<int,int> >::const_iterator iter = v.begin();iter != v.end(); ++iter ) {
        table_put(*iter);
    }
    table_disp();
}

[Update]
It is calculated to be a square or a rectangle in the case if the four angles within the Points, which entered=* and !=0."Regardless of the fact that inside the square or rectangle containing 0"
Like:

__1 2 3 4 5 
1 * 0 * 0 * 
2 0 0 * 0 * 
3 * 0 * * 0

Here is squares=1 (1,1)&(3,1)&(1,3)&(3,3) and Rectangle =2 the first (3,1)&(3,2)&(5,1)&(5,2) the second (1,1)&(3,1)&(1,3)&(3,3) 2) the count beginning from the first nearest point to (1,1) to the End of the Table in Backtracking Method.

Posted 23-Dec-16 21:46pm

Jeha 300

Updated 24-Dec-16 13:53pm

Patrice T

v10

Add a Solution

Comments

OriginalGriff 24-Dec-16 4:07am

And?
Where is the question?
Where are you stuck?
What help do you need?

Patrice T 24-Dec-16 5:35am

And you have a question ?
Explain your problem.
Use Improve question to update your question.

Patrice T 24-Dec-16 5:36am

What is the problem ?
Use Improve question to update your question.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2016-12-24T00:14:00

What is supposed to do the program ?
What is the problem ?

[Update]

Quote:
I need Help to complete the code with Backtracking Algorithm to Count All the rectangles and squares which Determinants between the Entered points " * "

Remember that we don't know what the program is supposed to do.
Give more details and show example.
Use Improve question to update your question.

[Update]
In your example, I see only 2 squares, first is (1,1)&(1,2)&(1,3)&(2,1)&(2,2)&(2,3)&(3,1)&(3,2)&(3,3) and second is (2,5).
You need to tell us the rules for finding the rectangles and squares.

[Update]
After your last update,

Quote:
the count beginning from the first nearest point to (1,1) to the End of the Table in Backtracking Method.

As I understand the question, there is no need of backtracking method, the method don't fit the problem. The method to solve the problem is nested loops.

C++

// square size is (v1, h1) to (v2, h2)
for(int v1 = 0; v1<size; ++v1) { // Upper
    for(int h1 = 0; h1<size; ++h1) { // Left
        if (table[v1][h1]== "*") {// Check if possible
            // set lower
                // set right
                    // check if other points
                        // filled conditions
                        // print solution
        }
    }
}

Since it smell like HomeWork, I let you complete the code.
As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

[Update]
Your comment was not readable. Please update your question with counting code and explain actual problem.
Use Improve question to update your question.

To downvoters: Comments don't work. posted comments just vanish.