Click here to Skip to main content
15,901,035 members
Please Sign up or sign in to vote.
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
Updated 24-Dec-16 13:53pm
v10
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

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.
 
Share this answer
 
v5
Comments
Jeha 300 24-Dec-16 7:32am    
I need Help to complete the code with Backtracking Algorithm to Count All the rectangles and squares which Determinants between the Entered points " * "
Jeha 300 24-Dec-16 13:29pm    
1) 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.
Jeha 300 25-Dec-16 9:53am    
Thank You For Your Help, I tried to Do what I understood, the code cheeked if the four points are = '*' and All the smallest Squares and Rectangles are counted but problem is the Largest one didn't count:
The code is :
void Counter (unsigned int S, unsigned int R)
{
S=0;
R=0;

for(int v1=0; v1<size; ++v1) ///upper
{
for(int h1=0; h1<size; h1++) ///Left
{
if(table[v1][h1]=='*')
{
if (table[v1][h1+1]=='*')
{
if (table[v1+1][h1+1]=='*')
{
if (table[v1+1][h1]=='*')
{
S++;

}
}
}
}

}
}
cout<<"\n The Number Of Squares = "<<S;
// Rectangle
for(int v1 = 0; v1<size; ++v1) /// Upper
{
for(int h1 = 0; h1<size; ++h1) /// Left
{
if (table[v1][h1]=='*') /// Check if possible
{
if(table[v1+2][h1]==char'*') /// set lower
{
if(table[v1][h1+1]=='*')
{
if(table[v1+2][h1+1]=='*')/// set right
R++;
}
}
}
if (table[v1][h1]=='*')
{
if(table[v1][h1+1]=='*')
{
if (table[v1+1][h1+2]=='*')
{
if(table[v1+1][h1+1]=='*')
R++;
}

}

}
}
}


cout<<"\n The Number Of Rectangles = "<<R; /// print solution
}

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900