tag:blogger.com,1999:blog-32573612391184371972024-03-18T21:21:37.475-07:00I recurse YOU !Zabir Al Nazi Nabilhttp://www.blogger.com/profile/02906242193437991438noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3257361239118437197.post-66684334652533218072016-03-31T12:33:00.002-07:002016-03-31T12:33:34.816-07:00UVa 12375 - Truchet Tiling<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMjr2YMcUqzkvZ5f8EFROWDOUQRu98isW9JfHMF6k0j7yC9A0LI1CgiRA9OWV3SjbQvgD7NGSs0xQDnTzr-2Qm2wRck1ftlFSPE1bfS6K-7GW7WXfQ-BO211nbfJG-1NMlU2ytfOodFAw/s1600/Untitled.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="130" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMjr2YMcUqzkvZ5f8EFROWDOUQRu98isW9JfHMF6k0j7yC9A0LI1CgiRA9OWV3SjbQvgD7NGSs0xQDnTzr-2Qm2wRck1ftlFSPE1bfS6K-7GW7WXfQ-BO211nbfJG-1NMlU2ytfOodFAw/s320/Untitled.png" width="320" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
The tricky part of the solution is to realize how the color is flowing from cell to cell (regions).<br />
We have two types of motifs 0 and 1. I have divided the motifs into 4 regions. In motif - 0 we have<br />
regions 1,2,3,4 and in motif - 1 we have regions 5,6,7,8.<br />
So,we will go from cell to cell and add the major region's area to solution and mark that region visited.<br />
For region 1,4,6,7 we will add PI/4 (Pi*(r^2)/4) and for other regions we will add (4 - PI/2)/2 to<br />
solution.<br />
And about the movement , look at the figure we can't go to any cell from a certain cell<br />
.For example,we can only go upward and left from region 1.Once We are in some cell if it's not<br />
visited (if it's visited we have already added it's area to solution) and it's a valid cell(not out of the boundary) then we add that cell's/region's area to the <br />
solution.<br />
<br />
Code : -<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #eeeedd; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: forestgreen;">/****************************************</span>
<span style="color: forestgreen;">Cat Got Bored</span>
<span style="color: forestgreen;">*****************************************/</span>
<span style="color: #1e889b;">#include <bits/stdc++.h></span>
<span style="color: #1e889b;">#define loop(i,s,e) for(int i = s;i<e;i++) </span><span style="color: forestgreen;">//excluding end point</span>
<span style="color: #1e889b;">#define pb(a) push_back(a)</span>
<span style="color: #1e889b;">#define sqr(x) ((x)*(x))</span>
<span style="color: #1e889b;">#define CIN ios_base::sync_with_stdio(0); cin.tie(0);</span>
<span style="color: #1e889b;">#define ll long long</span>
<span style="color: #1e889b;">#define ull unsigned long long</span>
<span style="color: #1e889b;">#define SZ(a) int(a.size())</span>
<span style="color: #1e889b;">#define read() freopen("input.txt", "r", stdin)</span>
<span style="color: #1e889b;">#define write() freopen("output.txt", "w", stdout)</span>
<span style="color: #1e889b;">#define ms(a,b) memset(a, b, sizeof(a))</span>
<span style="color: #1e889b;">#define all(v) v.begin(), v.end()</span>
<span style="color: #1e889b;">#define PI acos(-1.0)</span>
<span style="color: #1e889b;">#define pf printf</span>
<span style="color: #1e889b;">#define sfi(a) scanf("%d",&a);</span>
<span style="color: #1e889b;">#define sfii(a,b) scanf("%d %d",&a,&b);</span>
<span style="color: #1e889b;">#define sfl(a) scanf("%lld",&a);</span>
<span style="color: #1e889b;">#define sfll(a,b) scanf("%lld %lld",&a,&b);</span>
<span style="color: #1e889b;">#define mp make_pair</span>
<span style="color: #1e889b;">#define paii pair<int, int></span>
<span style="color: #1e889b;">#define padd pair<dd, dd></span>
<span style="color: #1e889b;">#define pall pair<ll, ll></span>
<span style="color: #1e889b;">#define fs first</span>
<span style="color: #1e889b;">#define sc second</span>
<span style="color: #1e889b;">#define CASE(t) printf("Case %d:\n",++t) </span><span style="color: forestgreen;">// t initialized 0</span>
<span style="color: #1e889b;">#define INF 9999999999999 </span><span style="color: forestgreen;">//10e9</span>
<span style="color: #1e889b;">#define EPS 1e-9</span>
<span style="color: darkmagenta; font-weight: bold;">using</span> <span style="color: darkmagenta; font-weight: bold;">namespace</span> std;
<span style="color: forestgreen;">//Graph Construction</span>
<span style="color: #a7a7a7; font-weight: bold;">int</span> rowMove[<span style="color: #b452cd;">9</span>][<span style="color: #b452cd;">3</span>];
<span style="color: #a7a7a7; font-weight: bold;">int</span> colMove[<span style="color: #b452cd;">9</span>][<span style="color: #b452cd;">3</span>];
<span style="color: darkmagenta; font-weight: bold;">const</span> <span style="color: #a7a7a7; font-weight: bold;">int</span> callRM[] = {<span style="color: #b452cd;">0</span>,<span style="color: #b452cd;">0</span>,<span style="color: #b452cd;">1</span>,<span style="color: #b452cd;">1</span>};
<span style="color: darkmagenta; font-weight: bold;">const</span> <span style="color: #a7a7a7; font-weight: bold;">int</span> callCM[] = {<span style="color: #b452cd;">0</span>,<span style="color: #b452cd;">1</span>,<span style="color: #b452cd;">0</span>,<span style="color: #b452cd;">1</span>};
<span style="color: #a7a7a7; font-weight: bold;">int</span> RR,CC;
<span style="color: #a7a7a7; font-weight: bold;">int</span> graph[<span style="color: #b452cd;">205</span>][<span style="color: #b452cd;">205</span>];
<span style="color: #a7a7a7; font-weight: bold;">bool</span> visited[<span style="color: #b452cd;">205</span>][<span style="color: #b452cd;">205</span>];
<span style="color: #a7a7a7; font-weight: bold;">void</span> <span style="color: #008b45;">graph_init</span>()
{
rowMove[<span style="color: #b452cd;">1</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">0</span>; rowMove[<span style="color: #b452cd;">1</span>][<span style="color: #b452cd;">1</span>] = -<span style="color: #b452cd;">1</span>;rowMove[<span style="color: #b452cd;">1</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">0</span>;
colMove[<span style="color: #b452cd;">1</span>][<span style="color: #b452cd;">0</span>] =-<span style="color: #b452cd;">1</span>; colMove[<span style="color: #b452cd;">1</span>][<span style="color: #b452cd;">1</span>] =<span style="color: #b452cd;">0</span>; colMove[<span style="color: #b452cd;">1</span>][<span style="color: #b452cd;">2</span>] =<span style="color: #b452cd;">0</span>;
rowMove[<span style="color: #b452cd;">2</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">0</span> ;rowMove[<span style="color: #b452cd;">2</span>][<span style="color: #b452cd;">1</span>] = -<span style="color: #b452cd;">1</span> ;rowMove[<span style="color: #b452cd;">2</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">1</span> ;
colMove[<span style="color: #b452cd;">2</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">1</span> ; colMove[<span style="color: #b452cd;">2</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">0</span> ; colMove[<span style="color: #b452cd;">2</span>][<span style="color: #b452cd;">2</span>] = -<span style="color: #b452cd;">1</span> ;
rowMove[<span style="color: #b452cd;">3</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">0</span> ;rowMove[<span style="color: #b452cd;">3</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">1</span> ;rowMove[<span style="color: #b452cd;">3</span>][<span style="color: #b452cd;">2</span>] = -<span style="color: #b452cd;">1</span> ;
colMove[<span style="color: #b452cd;">3</span>][<span style="color: #b452cd;">0</span>] = -<span style="color: #b452cd;">1</span>;colMove[<span style="color: #b452cd;">3</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">0</span>;colMove[<span style="color: #b452cd;">3</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">1</span>;
rowMove[<span style="color: #b452cd;">4</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">0</span> ;rowMove[<span style="color: #b452cd;">4</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">1</span> ;rowMove[<span style="color: #b452cd;">4</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">0</span> ;
colMove[<span style="color: #b452cd;">4</span>][<span style="color: #b452cd;">0</span>] =<span style="color: #b452cd;">1</span>;colMove[<span style="color: #b452cd;">4</span>][<span style="color: #b452cd;">1</span>] =<span style="color: #b452cd;">0</span>;colMove[<span style="color: #b452cd;">4</span>][<span style="color: #b452cd;">2</span>] =<span style="color: #b452cd;">0</span>;
rowMove[<span style="color: #b452cd;">5</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">0</span>;rowMove[<span style="color: #b452cd;">5</span>][<span style="color: #b452cd;">1</span>] = -<span style="color: #b452cd;">1</span>;rowMove[<span style="color: #b452cd;">5</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">1</span>;
colMove[<span style="color: #b452cd;">5</span>][<span style="color: #b452cd;">0</span>] = -<span style="color: #b452cd;">1</span>;colMove[<span style="color: #b452cd;">5</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">0</span>;colMove[<span style="color: #b452cd;">5</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">1</span>;
rowMove[<span style="color: #b452cd;">6</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">0</span>;rowMove[<span style="color: #b452cd;">6</span>][<span style="color: #b452cd;">1</span>] = -<span style="color: #b452cd;">1</span>;rowMove[<span style="color: #b452cd;">6</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">0</span>;
colMove[<span style="color: #b452cd;">6</span>][<span style="color: #b452cd;">0</span>] =<span style="color: #b452cd;">1</span>;colMove[<span style="color: #b452cd;">6</span>][<span style="color: #b452cd;">1</span>] =<span style="color: #b452cd;">0</span>;colMove[<span style="color: #b452cd;">6</span>][<span style="color: #b452cd;">2</span>] =<span style="color: #b452cd;">0</span>;
rowMove[<span style="color: #b452cd;">7</span>][<span style="color: #b452cd;">0</span>] =<span style="color: #b452cd;">0</span>;rowMove[<span style="color: #b452cd;">7</span>][<span style="color: #b452cd;">1</span>] =<span style="color: #b452cd;">1</span>;rowMove[<span style="color: #b452cd;">7</span>][<span style="color: #b452cd;">2</span>] =<span style="color: #b452cd;">0</span>;
colMove[<span style="color: #b452cd;">7</span>][<span style="color: #b452cd;">0</span>] = -<span style="color: #b452cd;">1</span>;colMove[<span style="color: #b452cd;">7</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">0</span>;colMove[<span style="color: #b452cd;">7</span>][<span style="color: #b452cd;">2</span>] = <span style="color: #b452cd;">0</span>;
rowMove[<span style="color: #b452cd;">8</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">0</span>;rowMove[<span style="color: #b452cd;">8</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">1</span>;rowMove[<span style="color: #b452cd;">8</span>][<span style="color: #b452cd;">2</span>] = -<span style="color: #b452cd;">1</span>;
colMove[<span style="color: #b452cd;">8</span>][<span style="color: #b452cd;">0</span>] = <span style="color: #b452cd;">1</span>;colMove[<span style="color: #b452cd;">8</span>][<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">0</span>;colMove[<span style="color: #b452cd;">8</span>][<span style="color: #b452cd;">2</span>] = -<span style="color: #b452cd;">1</span>;
}
<span style="color: #a7a7a7; font-weight: bold;">bool</span> <span style="color: #008b45;">valid</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> r,<span style="color: #a7a7a7; font-weight: bold;">int</span> c)
{
<span style="color: darkmagenta; font-weight: bold;">if</span>(r<<span style="color: #b452cd;">1</span> || r><span style="color: #b452cd;">2</span>*RR || c<<span style="color: #b452cd;">1</span> || c><span style="color: #b452cd;">2</span>*CC)
<span style="color: darkmagenta; font-weight: bold;">return</span> <span style="color: #658b00;">false</span>;
<span style="color: darkmagenta; font-weight: bold;">return</span> <span style="color: #658b00;">true</span>;
}
<span style="color: #a7a7a7; font-weight: bold;">double</span> <span style="color: #008b45;">area_grid</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> r,<span style="color: #a7a7a7; font-weight: bold;">int</span> c)
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> grid_no = graph[r][c];
<span style="color: #a7a7a7; font-weight: bold;">int</span> g_n = grid_no;
<span style="color: darkmagenta; font-weight: bold;">if</span>(g_n == <span style="color: #b452cd;">1</span> || g_n == <span style="color: #b452cd;">4</span> || g_n == <span style="color: #b452cd;">6</span> || g_n == <span style="color: #b452cd;">7</span> )
<span style="color: darkmagenta; font-weight: bold;">return</span> ((PI)/<span style="color: #b452cd;">4.00000</span>)*<span style="color: #b452cd;">1.00000</span>;
<span style="color: darkmagenta; font-weight: bold;">else</span>
<span style="color: darkmagenta; font-weight: bold;">return</span> (<span style="color: #b452cd;">4.0000000</span> - (PI/<span style="color: #b452cd;">2.000000</span>)*<span style="color: #b452cd;">1.000000</span>)/<span style="color: #b452cd;">2.0000000</span>;
}
<span style="color: #a7a7a7; font-weight: bold;">double</span> <span style="color: #008b45;">area</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> r,<span style="color: #a7a7a7; font-weight: bold;">int</span> c)
{
<span style="color: darkmagenta; font-weight: bold;">if</span>(visited[r][c])
<span style="color: darkmagenta; font-weight: bold;">return</span> <span style="color: #b452cd;">0.00000000</span>;
<span style="color: darkmagenta; font-weight: bold;">if</span>(!valid(r,c))
<span style="color: darkmagenta; font-weight: bold;">return</span> <span style="color: #b452cd;">0.00000000</span>;
visited[r][c] = <span style="color: #658b00;">true</span>;
<span style="color: #a7a7a7; font-weight: bold;">double</span> partial_area = <span style="color: #b452cd;">0.00000000</span>;
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> i=<span style="color: #b452cd;">0</span>; i<<span style="color: #b452cd;">3</span>; i++)
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> r_pp = r + rowMove[ graph[r][c] ][i];
<span style="color: #a7a7a7; font-weight: bold;">int</span> c_pp = c + colMove[ graph[r][c] ][i];
partial_area += area(r_pp,c_pp);
}
<span style="color: darkmagenta; font-weight: bold;">return</span> area_grid(r,c) + partial_area ;
}
<span style="color: #a7a7a7; font-weight: bold;">int</span> <span style="color: #008b45;">main</span>()
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> tc;
cin>>tc;
<span style="color: #a7a7a7; font-weight: bold;">int</span> cas = <span style="color: #b452cd;">0</span>;
graph_init();
<span style="color: darkmagenta; font-weight: bold;">while</span>(tc--)
{
cin>>RR>>CC;
<span style="color: #a7a7a7; font-weight: bold;">int</span> rrr = <span style="color: #b452cd;">1</span> ;
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> r = <span style="color: #b452cd;">0</span>; r<RR; r++)
{
string sss;
cin>>sss;
<span style="color: #a7a7a7; font-weight: bold;">int</span> ccc = <span style="color: #b452cd;">1</span> ;
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> c = <span style="color: #b452cd;">0</span>; c<CC; c++)
{
<span style="color: darkmagenta; font-weight: bold;">if</span>(sss[c]==<span style="color: #cd5555;">'0'</span>)
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> r_p = <span style="color: #b452cd;">2</span>*r + <span style="color: #b452cd;">1</span>;
<span style="color: #a7a7a7; font-weight: bold;">int</span> c_p = <span style="color: #b452cd;">2</span>*c + <span style="color: #b452cd;">1</span>;
graph[r_p][c_p] = <span style="color: #b452cd;">1</span>;
graph[r_p][c_p+<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">2</span>;
graph[r_p+<span style="color: #b452cd;">1</span>][c_p] = <span style="color: #b452cd;">3</span>;
graph[r_p+<span style="color: #b452cd;">1</span>][c_p+<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">4</span>;
}
<span style="color: darkmagenta; font-weight: bold;">if</span>(sss[c]==<span style="color: #cd5555;">'1'</span>)
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> r_p = <span style="color: #b452cd;">2</span>*r + <span style="color: #b452cd;">1</span>;
<span style="color: #a7a7a7; font-weight: bold;">int</span> c_p = <span style="color: #b452cd;">2</span>*c + <span style="color: #b452cd;">1</span>;
graph[r_p][c_p] = <span style="color: #b452cd;">5</span>;
graph[r_p][c_p+<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">6</span>;
graph[r_p+<span style="color: #b452cd;">1</span>][c_p] = <span style="color: #b452cd;">7</span>;
graph[r_p+<span style="color: #b452cd;">1</span>][c_p+<span style="color: #b452cd;">1</span>] = <span style="color: #b452cd;">8</span>;
}
}
}
<span style="color: forestgreen;">/*</span>
<span style="color: forestgreen;"> int i,j;</span>
<span style="color: forestgreen;"> loop(i,1,2*RR+1)</span>
<span style="color: forestgreen;"> {</span>
<span style="color: forestgreen;"> loop(j,1,2*CC+1)</span>
<span style="color: forestgreen;"> {</span>
<span style="color: forestgreen;"> cout<<graph[i][j];</span>
<span style="color: forestgreen;"> }</span>
<span style="color: forestgreen;"> cout<<endl;</span>
<span style="color: forestgreen;"> }</span>
<span style="color: forestgreen;">*/</span>
<span style="color: forestgreen;">//calling inititialization</span>
CASE(cas);
<span style="color: #a7a7a7; font-weight: bold;">int</span> Q;
cin>>Q;
<span style="color: darkmagenta; font-weight: bold;">while</span>(Q--)
{
ms(visited,<span style="color: #658b00;">false</span>);
<span style="color: #a7a7a7; font-weight: bold;">int</span> r_call , c_call;
cin>>r_call>>c_call;
<span style="color: #a7a7a7; font-weight: bold;">double</span> ans = <span style="color: #b452cd;">0.00000000</span>;
<span style="color: darkmagenta; font-weight: bold;">if</span>((r_call%<span style="color: #b452cd;">2</span>==<span style="color: #b452cd;">0</span> && c_call%<span style="color: #b452cd;">2</span>==<span style="color: #b452cd;">1</span>) || (r_call%<span style="color: #b452cd;">2</span>==<span style="color: #b452cd;">1</span> && c_call%<span style="color: #b452cd;">2</span>==<span style="color: #b452cd;">0</span>))
{
pf(<span style="color: #cd5555;">"%.4f\n"</span>,ans);
<span style="color: darkmagenta; font-weight: bold;">continue</span>;
}
<span style="color: #a7a7a7; font-weight: bold;">int</span> flag = <span style="color: #b452cd;">0</span>;
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> ii= <span style="color: #b452cd;">0</span>; ii<<span style="color: #b452cd;">4</span>; ii++)
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> <span style="color: #a7a7a7; font-weight: bold;">r_t</span> = r_call + callRM[ii];
<span style="color: #a7a7a7; font-weight: bold;">int</span> <span style="color: #a7a7a7; font-weight: bold;">c_t</span> = c_call + callCM[ii];
<span style="color: darkmagenta; font-weight: bold;">if</span>(!valid(<span style="color: #a7a7a7; font-weight: bold;">r_t</span>,<span style="color: #a7a7a7; font-weight: bold;">c_t</span>))
<span style="color: darkmagenta; font-weight: bold;">continue</span>;
<span style="color: darkmagenta; font-weight: bold;">if</span>(graph[<span style="color: #a7a7a7; font-weight: bold;">r_t</span>][<span style="color: #a7a7a7; font-weight: bold;">c_t</span>]==<span style="color: #b452cd;">2</span> || graph[<span style="color: #a7a7a7; font-weight: bold;">r_t</span>][<span style="color: #a7a7a7; font-weight: bold;">c_t</span>]==<span style="color: #b452cd;">3</span> ||graph[<span style="color: #a7a7a7; font-weight: bold;">r_t</span>][<span style="color: #a7a7a7; font-weight: bold;">c_t</span>]==<span style="color: #b452cd;">5</span> ||graph[<span style="color: #a7a7a7; font-weight: bold;">r_t</span>][<span style="color: #a7a7a7; font-weight: bold;">c_t</span>]==<span style="color: #b452cd;">8</span>)
{
ans = area(<span style="color: #a7a7a7; font-weight: bold;">r_t</span>,<span style="color: #a7a7a7; font-weight: bold;">c_t</span>);
flag = <span style="color: #b452cd;">1</span>;
<span style="color: darkmagenta; font-weight: bold;">break</span>;
}
}
<span style="color: darkmagenta; font-weight: bold;">if</span>(flag == <span style="color: #b452cd;">1</span>)
pf(<span style="color: #cd5555;">"%.4f\n"</span>,ans);
<span style="color: darkmagenta; font-weight: bold;">else</span>
{
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> ii= <span style="color: #b452cd;">0</span>; ii<<span style="color: #b452cd;">4</span>; ii++)
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> <span style="color: #a7a7a7; font-weight: bold;">r_t</span> = r_call + callRM[ii];
<span style="color: #a7a7a7; font-weight: bold;">int</span> <span style="color: #a7a7a7; font-weight: bold;">c_t</span> = c_call + callCM[ii];
<span style="color: darkmagenta; font-weight: bold;">if</span>(valid(<span style="color: #a7a7a7; font-weight: bold;">r_t</span>,<span style="color: #a7a7a7; font-weight: bold;">c_t</span>))
{
ans = area(<span style="color: #a7a7a7; font-weight: bold;">r_t</span>,<span style="color: #a7a7a7; font-weight: bold;">c_t</span>);
pf(<span style="color: #cd5555;">"%.4f\n"</span>,ans);
<span style="color: darkmagenta; font-weight: bold;">break</span>;
}
}
}
}
}
<span style="color: darkmagenta; font-weight: bold;">return</span> <span style="color: #b452cd;">0</span>;
}
</pre>
</td></tr>
</tbody></table>
</div>
</div>
Zabir Al Nazi Nabilhttp://www.blogger.com/profile/02906242193437991438noreply@blogger.com0tag:blogger.com,1999:blog-3257361239118437197.post-61323814917308310642016-03-17T13:18:00.001-07:002016-03-31T12:39:53.858-07:00All palindromic contiguous substring !<div dir="ltr" style="text-align: left;" trbidi="on">
This is so far what I have come up with ! I think there are better ways to do this . : ) )<br />
But it 's working for my problem<br />
:-P<br />
<br />
<br />
Here's to the code - ><br />
<br />
//Sorry this doesn't work ! I will edit it when I'm busy :-/<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #eeeedd; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: forestgreen;">/*</span>
<span style="color: forestgreen;">@_@</span>
<span style="color: forestgreen;">catGotBored</span>
<span style="color: forestgreen;">@_@</span>
<span style="color: forestgreen;">*/</span>
<span style="color: #1e889b;">#include<bits/stdc++.h></span>
<span style="color: darkmagenta; font-weight: bold;">using</span> <span style="color: darkmagenta; font-weight: bold;">namespace</span> std;
<span style="color: #a7a7a7; font-weight: bold;">int</span> isPalindrome[<span style="color: #b452cd;">100</span>][<span style="color: #b452cd;">100</span>];
map<string,<span style="color: #a7a7a7; font-weight: bold;">int</span>>isThere;
<span style="color: #a7a7a7; font-weight: bold;">void</span> <span style="color: #008b45;">all_palindromic_conti_sub_str</span>(string s)
{
<span style="color: #a7a7a7; font-weight: bold;">int</span> N = s.length();
<span style="color: forestgreen;">//Lets find all such palindromes with length 1 . Easy , huh ?</span>
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> idx = <span style="color: #b452cd;">0</span>; idx<N; idx++)
isPalindrome[idx][idx] = <span style="color: #b452cd;">1</span>;
<span style="color: forestgreen;">//Lets find all such palindromes with length 2 . Easy again !!</span>
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> idx = <span style="color: #b452cd;">0</span>; idx < N -<span style="color: #b452cd;">1</span> ; idx++)
isPalindrome[idx][idx+<span style="color: #b452cd;">1</span>] = (s[idx] == s[idx+<span style="color: #b452cd;">1</span>] );
<span style="color: forestgreen;">//Now,lets do it for all lengths < = N</span>
<span style="color: forestgreen;">//Idea is simple :</span>
<span style="color: forestgreen;">//If I know s[i...j] is a palindrome then s[i-1.....j+1] is a palindrome</span>
<span style="color: forestgreen;">//if and only if s[i-1] == s[j+1]</span>
<span style="color: forestgreen;">//O(N^2) for marking only</span>
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> idx = <span style="color: #b452cd;">0</span> ,len = <span style="color: #b452cd;">3</span>; idx <= N -len; idx++,len++)
{
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> jdx = idx + len -<span style="color: #b452cd;">1</span> ; jdx < N ; jdx ++ )
{
isPalindrome[idx][jdx] = isPalindrome[idx+<span style="color: #b452cd;">1</span>][jdx-<span style="color: #b452cd;">1</span>] & s[idx] == s[jdx] ;
}
}
/
<span style="color: forestgreen;">//Bad approach : O(N^3 * log (N)) -> Need to do better //</span>
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> ff = <span style="color: #b452cd;">0</span>; ff<N; ff++)
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> ss = <span style="color: #b452cd;">0</span>; ss<N; ss++)
<span style="color: darkmagenta; font-weight: bold;">if</span>(isPalindrome[ff][ss])
{
string temp;
<span style="color: darkmagenta; font-weight: bold;">for</span>(<span style="color: #a7a7a7; font-weight: bold;">int</span> xfsx = ff ; xfsx <= ss ; xfsx++)
temp+=s[xfsx] ; <span style="color: forestgreen;">// cout<<s[xfsx]; //Every palindromes non distinct ones too</span>
<span style="color: darkmagenta; font-weight: bold;">if</span>(isThere[temp] == <span style="color: #b452cd;">0</span>)
{
cout<<temp;
isThere[temp]++;
cout<<endl;
}
}
}
<span style="color: #a7a7a7; font-weight: bold;">int</span> <span style="color: #008b45;">main</span>()
{
string str_ = <span style="color: #cd5555;">"aassaa"</span>;
memset(isPalindrome,<span style="color: #b452cd;">0</span>,<span style="color: darkmagenta; font-weight: bold;">sizeof</span>(isPalindrome)); <span style="color: forestgreen;">// just for nothing </span>
all_palindromic_conti_sub_str(str_);
<span style="color: darkmagenta; font-weight: bold;">return</span> <span style="color: #b452cd;">0</span>;
}
</pre>
</td></tr>
</tbody></table>
</div>
</div>
Zabir Al Nazi Nabilhttp://www.blogger.com/profile/02906242193437991438noreply@blogger.com0