#include
#include
int x[10][10] = {
{ 1, 1, 1, 1, 1, 1, 5, 1, 1, 1,},
{ 1, 1, 1, 1, 1, 1, 4, 1, 1, 1,},
{ 1, 1, 1, 1, 1, 1, 8, 1, 1, 1,},
{ 1, 1, 1, 1, 5, 4, 10, 1, 1, 1,},
{ 1, 1, 1, 1, 4, 1, 10, 10, 1, 1,},
{ 1, 1, 1, 1, 5, 5, 10, 10, 10, 10,},
{ 1, 1, 5, 6, 1, 5, 11, 1, 1, 1,},
{ 1, 1, 3, 1, 1, 1, 10, 1, 1, 1,},
{ 1, 2, 2, 1, 1, 1, 1, 1, 1, 1,},
{ 2, 1, 10, 10, 10, 10, 10, 10, 1, 1,},
};
#define PA 0x01
#define AT 0x02
struct dot {
int x;
int y;
};
detect_line2(int N, int g[N][N], int a[N][N], int s,
struct dot start[], int set_bit)
{
struct dot nextline[2*N], myline[2*N];
int n, m, i;
for (i = 0; i < s; i++) {
a[start[i].x][start[i].y] |= set_bit;
}
memcpy(myline, start, sizeof(struct dot) * s);
n = s;
again:
m = 0;
for (i = 0; i < n; i++) {
int x = myline[i].x, y = myline[i].y;
if (x-1 >= 0) {
if (!(a[x-1][y] & set_bit) && g[x-1][y] >= g[x][y]) {
nextline[m].x = x-1;
nextline[m].y = y;
a[x-1][y] |= set_bit;
m++;
}
}
if (x+1 < N) {
if (!(a[x+1][y] & set_bit) && g[x+1][y] >= g[x][y]) {
nextline[m].x = x+1;
nextline[m].y = y;
a[x+1][y] |= set_bit;
m++;
}
}
if (y-1 >= 0) {
if (!(a[x][y-1] & set_bit) && g[x][y-1] >= g[x][y]) {
nextline[m].x = x;
nextline[m].y = y - 1;
a[x][y-1] |= set_bit;
m++;
}
}
if (y+1 < N) {
if (!(a[x][y+1] & set_bit) && g[x][y+1] >= g[x][y]) {
nextline[m].x = x;
nextline[m].y = y+1;
a[x][y+1] |= set_bit;
m++;
}
}
}
if (m == 0) {
return;
} else {
n = m;
memcpy(myline, nextline, sizeof(struct dot) * m);
goto again;
}
}
detect2(int G, int g[G][G])
{
int a[G][G];
int i, j, n = 0;
struct dot myline[2*G];
memset(a, 0, sizeof(a));
for (i= 0; i< G; i++) {
myline[n].x = i;
myline[n].y = G-1;
n++;
}
detect_line2(G, g, a, n, myline, AT);
n = 0;
for (i= 0; i< G; i++) {
myline[n].x = i;
myline[n].y = 0;
n++;
}
detect_line2(G, g, a, n, myline, PA);
for (i = 0; i < G; i++) {
for (j = 0; j < G; j++) {
if (a[i][j] == (AT|PA)) {
printf("(%2d) ", g[i][j]);
} else {
printf(" %2d ", g[i][j]);
}
}
printf("\n");
}
}
detect_line(int G, int g[G][G], int a[G][G], int x, int y,
int last, int set_bit)
{
if (x < 0 || x >= G || y < 0 || y >= G) {
return;
}
if ((a[x][y] & set_bit)) {
return;
}
if (g[x][y] >= last) {
a[x][y] |= set_bit;
detect_line(G, g, a, x+1, y, g[x][y], set_bit);
detect_line(G, g, a, x-1, y, g[x][y], set_bit);
detect_line(G, g, a, x, y+1, g[x][y], set_bit);
detect_line(G, g, a, x, y-1, g[x][y], set_bit);
}
return;
}
detect(int G, int g[G][G])
{
int a[G][G];
int i, j;
memset(a, 0, sizeof(a));
for (i= 0; i< G; i++) {
detect_line(G, g, a, i, G-1, 0, AT);
}
for (i= 0; i< G; i++) {
detect_line(G, g, a, i, 0, 0, PA);
}
for (i = 0; i < G; i++) {
for (j = 0; j < G; j++) {
if (a[i][j] == (AT|PA)) {
printf("(%2d) ", g[i][j]);
} else {
printf(" %2d ", g[i][j]);
}
}
printf("\n");
}
}
main()
{
detect(10, x);
printf("\n");
detect2(10, x);
}
