-
Notifications
You must be signed in to change notification settings - Fork 0
/
heat.cpp
127 lines (123 loc) · 2.95 KB
/
heat.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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/* Fighting the Heat */
#include <stdio.h>
#include <iostream>
#include <string>
#define MAX_L 40
#define MAX_W 400
using namespace std;
int
main(void)
{
int n, m, k;
string d[MAX_W];
bool in_d[MAX_L][MAX_L] = {false};
char g[MAX_L][MAX_L];
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < k; i++)
cin >> d[i];
for( int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
/* Aho-Corasik would be a pretty neat overkill.
* brut forcing with find instead.
*/
/* horizontal */
for (int i = 0; i < n; i++) {
string rline;
for (int idx = m - 1; idx > -1; idx--)
rline.push_back(g[i][idx]);
for (int w = 0; w < k; w++) {
int w_size = d[w].size();
int found = string(g[i] + '\0').find(d[w]);
int rfound;
if (found != -1)
for (int idx = found; idx < w_size; idx++)
in_d[i][idx] = true;
rfound = rline.find(d[w]);
if (rfound != -1)
for (int idx = m - rfound; idx < w_size; idx++)
in_d[i][idx] = true;
}
}
/* vertical */
for (int j = 0; j < m; j++) {
int found, rfound;
string s, rs;
for (int i = 0; i < n; i++) {
s.push_back(g[i][j]);
rs.push_back(g[i][n - j]);
}
for (int w = 0; w < k; w++) {
int w_size = d[w].size();
if ((found = s.find(d[w])) != -1)
for (int idx = found; idx < w_size; idx++)
in_d[idx][j] = true;
if ((rfound = rs.find(d[w])) != -1)
for (int idx = n - rfound; idx < w_size; idx++)
in_d[idx][j] = true;
}
}
/* diagonal: top left - bottow right */
for (int idx = 0; idx < n + m; idx++) {
int a, cst_a, b, cst_b, l = 0;
string s, rs;
a = ((idx / (n - 1)) ? 0 : (n - 1) - idx);
b = ((idx / (n - 1)) ? idx - (n - 1) : 0);
cst_a = a;
cst_b = b;
while (a < n - 1 && b < m - 1) {
s.push_back(g[a++][b++]);
l++;
}
for (int i = 0; i < l; i++)
rs.push_back(g[a--][b--]);
for (int w = 0; w < k; w++) {
int w_size = d[w].size();
int found = s.find(d[w]);
int rfound = rs.find(d[w]);
if (found != -1)
for (int i = 0; i < w_size; i++)
in_d[a++][b++] = true;
a = cst_a;
b = cst_b;
if (rfound != -1)
for (int i = 0; i < w_size; i++)
in_d[a++][b++] = true;
}
}
/* diagonal: top right - bottow left */
for (int idx = 0; idx < n + m; idx++) {
int a, cst_a, b, cst_b, l = 0;
string s, rs;
a = ((idx / (m - 1)) ? 0 : idx - (m - 1));
b = ((idx / (m - 1)) ? idx : m - 1);
cst_a = a;
cst_b = b;
while (a < n - 1 && b > 0) {
s.push_back(g[a++][b--]);
l++;
}
for (int i = 0; i < l; i++)
rs.push_back(g[a--][b++]);
for (int w = 0; w < k; w++) {
int w_size = d[w].size();
int found = s.find(d[w]);
int rfound = rs.find(d[w]);
if (found != -1)
for (int i = 0; i < w_size; i++)
in_d[a++][b--] = true;
a = cst_a;
b = cst_b;
if (rfound != -1)
for (int i = 0; i < w_size; i++)
in_d[a++][b--] = true;
}
}
/* print the solution */
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (!in_d[i][j])
printf("%c", d[i][j]);
printf("\n");
return 0;
}