-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathBrideHuntOptimal.cpp
105 lines (93 loc) · 2.13 KB
/
BrideHuntOptimal.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<iostream>
#include<stack>
#include<climits>
using namespace std;
int find_distance(int x1,int y1){
int x=1, y=1;
return (x1-x) + (y1-y);
}
int main(){
/*
int m=2, n=9;
int arr[10][10] = {{1,0,1,1,0,1,1,1,1},{0,0,0,1,0,1,0,0,1}};
int m=6, n=6;
int arr[10][10] = {
{1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 1, 0},
{0, 0, 1, 1, 1, 0},
{0, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0},
};*/
int m=2, n=3;
int arr[10][10] = {{1,0,1},{0,0,0}};
int max_count=0, count=0;
arr[0][0] = 0;
stack<pair<int,int>> st;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
count = 0;
if(arr[i][j] == 1)
{
//Top Row
if( i>0 && arr[i-1][j] == 1 )
count++;
if( i>0 && j>0 && arr[i-1][j-1] == 1 )
count++;
if( i>0 && j+1<n && arr[i-1][j+1] == 1 )
count++;
//Same Row
if( j>0 && arr[i][j-1] == 1 )
count++;
if( j+1<n && arr[i][j+1] == 1 )
count++;
//Bottom Row
if( i+1<m && arr[i+1][j] == 1 )
count++;
if( i+1<m && j>0 && arr[i+1][j-1] == 1 )
count++;
if( i+1<m && j+1<n && arr[i+1][j+1] == 1 )
count++;
//cout<<i<<" : "<<j<<" : "<<count<<"\n";
if( count!=0 && count > max_count){
max_count = count;
while(!st.empty()){
st.pop();
}
st.push(make_pair(i,j));
}
else if(count!=0 && count == max_count){
st.push(make_pair(i,j));
}
}
}
}
if(max_count == 0){
cout<<"No Suitable Girl Found"<<"\n";
return 0;
}
int min_distance=INT_MAX, x_f, y_f;
if(st.size() == 1){
x_f = st.top().first;
y_f = st.top().second;
cout<<x_f+1<<" : "<<y_f+1<<" : "<<max_count;
}
else{
while(!st.empty()){
if( find_distance(st.top().first, st.top().second) < min_distance){
x_f = st.top().first;
y_f = st.top().second;
min_distance = find_distance(st.top().first, st.top().second);
}
else if(find_distance(st.top().first, st.top().second) == min_distance){
cout<<"Polygamy not allowed";
return 0;
}
st.pop();
}
cout<<x_f+1<<" : "<<y_f+1<<" : "<<max_count;
}
return 0;
}