C++

Forum

 
Modification of Flood fill ???

Pages: 123
closed account (ojEqDjzh)

Sub-Task Task # Result
(time)
1 0 AC
(1.180000)
1 1 AC
(0.340000)
1 2 TLE
(4.010000)
1 3 AC
(1.250000)
1 4 AC
(1.060000)
Subtask Score: 0.00% Result - TLE
2 5 TLE
(4.010000)
2 6 TLE
(4.010000)
2 7 TLE
(4.010000)
2 8 TLE
(4.010000)
2 9 TLE
(4.010000)
Subtask Score: 0.00% Result - TLE
3 10 TLE
(4.010000)
3 11 TLE
(4.010000)
3 12 TLE
(4.010000)
3 13 TLE
(4.010000)
3 14 TLE
(4.010000)
Subtask Score: 0.00% Result - TLE
Total Score = 0.00%
@Wasp can you please help?
I followed your psuedocode
hyfun (10)
please someone help me to sort this
only two cases are failing:


#include<bits/stdc++.h>
using namespace std;
int ROW,COL;
int key1=1,key2=1;
int M[2000][2000];
int visited[2000][2000];

int isSafe( int row, int col,int key)
{
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
((M[row][col]==key1||M[row][col]==key2)&& visited[row][col]!= key);
}

void DFS( int row, int col, int *count,int key)
{
static int rowNbr[] = { -1, 0, 0, 1};
static int colNbr[] = { 0, -1, 1, 0};

visited[row][col] = key;
for (int k = 0; k < 4; ++k)
{
if (isSafe( row + rowNbr[k], col + colNbr[k],key))
{
(*count)++;
DFS( row + rowNbr[k], col + colNbr[k],
count,key);
}
}
}
int largestRegion(int k)
{


int result = INT_MIN;
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j < COL; ++j)
{
if ((M[i][j]==key1 || M[i][j] ==key2) && visited[i][j]!=k )
{
int count = 1 ;
DFS( i, j, &count,k);
result = max(result , count);
}
}
}
return result ;
}

// Driver program to test above function
int main()
{
memset(visited, 0, sizeof(visited));
int n,m;
scanf("%d%d",&n,&m);
ROW=n;COL=m;
int t,S,count=1,Max=0;
// stack<int> Sta;
set<int> s;
for(int i =0;i<ROW;i++)
for(int j=0;j<COL;j++)
{scanf("%d",&t);M[i][j] = t;s.insert(t);}
S= s.size();
set<int>::iterator itr,it;
for(itr = s.begin();itr!=s.end();itr++)
for(it = itr;it!=s.end();it++)
{ key1 = (*itr);key2 = (*it); t = largestRegion(count);count++;;
Max= max(Max,t);
}
printf("%d",Max);

return 0;
}
rish123y (5)
@unstoppable13 can you provide any reference about what to use instead of memset ???
fll()
lastchance (6980)
Now it is no longer relevant ...

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
#include <iostream>
#include <sstream>
#include <utility>
#include <vector>
#include <stack>
#include <set>
using namespace std;

using matrix = vector<vector<int>>;
using pt = pair<int,int>;


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


struct connect
{
   bool idir = true, jdir = true;
};



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


bool operator < ( const pt &p, const pt &q )    // Define ordering, so as to put pts in a set
{
   if ( p.first < q.first ) return true;
   if ( p.first == q.first && p.second < q.second ) return true;
   return false;
}


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


int floodfill( int i1, int j1, int i2, int j2, const matrix &a, vector< vector<connect> > &c )
{
   int rows = a.size(), cols = a[0].size();
   int value1 = a[i1][j1], value2 = a[i2][j2];

   set<pt> fill;   fill.insert( { i1, j1 } );  fill.insert( { i2, j2 } );
   stack<pt> stk;   stk.push  ( { i1, j1 } );   stk.push  ( { i2, j2 } );

   int area = 2;

   // Standard floodfill; test s, n, w, e points and add to a stack
   while ( !stk.empty() )
   {
      pt p = stk.top();
      stk.pop();
         
      int i = p.first, j = p.second;
      int im = i - 1, ip = i + 1, jm = j - 1, jp = j + 1;
      p = pt( im, j );
      if ( im >= 0   && fill.find( p ) == fill.end() && ( a[im][j] == value1 || a[im][j] == value2 ) )
      {
         stk.push( p );   fill.insert( p );
         area++;
      }
      p = pt( ip, j );
      if ( ip < rows && fill.find( { ip, j } ) == fill.end() && ( a[ip][j] == value1 || a[ip][j] == value2 ) )
      {
         stk.push( p );   fill.insert( p );
         area++;
      }
      p = pt( i, jm );
      if ( jm >= 0   && fill.find( { i, jm } ) == fill.end() && ( a[i][jm] == value1 || a[i][jm] == value2 ) )
      {
         stk.push( p );   fill.insert( p );
         area++;
      }
      p = pt( i, jp );
      if ( jp < cols && fill.find( { i, jp } ) == fill.end() && ( a[i][jp] == value1 || a[i][jp] == value2 ) )
      {
         stk.push( p );   fill.insert( p );
         area++;
      }
   }

   // Turn off connectors so this fill won't be scanned again
   for ( pt p : fill )
   {
      int i = p.first, j = p.second;
      int im = i - 1, ip = i + 1, jm = j - 1, jp = j + 1;
      if ( im >= 0    && ( a[im][j ] == value1 || a[im][j ] == value2 ) ) c[im][j ].idir = false;
      if ( ip <  rows && ( a[ip][j ] == value1 || a[ip][j ] == value2 ) ) c[i ][j ].idir = false;
      if ( jm >= 0    && ( a[i ][jm] == value1 || a[i ][jm] == value2 ) ) c[i ][jm].jdir = false;
      if ( jp <  cols && ( a[i ][jp] == value1 || a[i ][jp] == value2 ) ) c[i ][j ].jdir = false;
   }

   return area;
}


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


int main()
{
   istream &in2 = cin;                 // Use this for actual input
   stringstream in(                    // Version for testing
                    "4 5       \n"
                    "1 1 2 3 1 \n"
                    "3 1 2 5 2 \n"
                    "5 2 1 5 6 \n"
                    "1 3 1 2 1 \n"
                  );

   // Read data
   int rows, cols;
   in >> rows >> cols;
   matrix a( rows, vector<int>( cols ) );
   vector< vector<connect> > c( rows, vector<connect>( cols ) );
   for ( int i = 0; i < rows; i++ )
   {
      for ( int j = 0; j < cols; j++ ) in >> a[i][j];
   }


   // Adjust connectors for equal adjacent values (indicator 0)
   bool different = false;
   int a0 = a[0][0];
   for ( int i = 0; i < rows; i++ )
   {
      for ( int j = 0; j < cols; j++ )
      {
         int value = a[i][j];
         if ( value != a0 ) different = true;
         if ( i < rows - 1 && a[i+1][j] == value ) c[i][j].idir = false;
         if ( j < cols - 1 && a[i][j+1] == value ) c[i][j].jdir = false;
      }
   }
   if ( !different )                                       // Deal with the trivial case ... all equal!
   {
      cout << rows * cols << '\n';
      return 0;
   }


   // Optimise fills; always start on an UNUSED, NON-EQUAL pair
   int maxArea = 0;
   for ( int i = 0; i < rows - 1; i++ )
   {
      for ( int j = 0; j < cols - 1; j++ )
      {
         if ( c[i][j].idir )
         {
            int area = floodfill( i, j, i + 1, j, a, c );
            if ( area > maxArea ) maxArea = area;
         }

         if ( c[i][j].jdir )
         {
            int area = floodfill( i, j, i, j + 1, a, c );
            if ( area > maxArea ) maxArea = area;
         }
      }
   }
   cout << maxArea << '\n';
}
Topic archived. No new replies allowed.
Pages: 123