|
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <string.h> |
|
#include "img.h" |
|
|
|
// image data (ppm format) |
|
static unsigned char buf[HEIGHT][WIDTH][3]; |
|
static int filecnt = 0; |
|
static char fname[100]; |
|
|
|
// direction vector |
|
int dx[4] = {0, -1, 0, 1}; |
|
int dy[4] = {-1, 0, 1, 0}; |
|
|
|
// using array like a queue |
|
Point que[4000]; |
|
int head = 0, tail = 0; |
|
|
|
int flag = 1; |
|
|
|
// maze data (20 * 20) |
|
char maze[21][21] = { |
|
"####################", |
|
"#.................S#", |
|
"#.####.####.######.#", |
|
"#.#......##.#....#.#", |
|
"#.######.##.####.#.#", |
|
"#..#...####....#.#.#", |
|
"#.##.#.#.#####.#.#.#", |
|
"#.####.#.#...#.#.#.#", |
|
"#..........###.#.#.#", |
|
"#.###..#.###...#.#.#", |
|
"#.#.#######..###...#", |
|
"#.........#.######.#", |
|
"#.#######.#.#......#", |
|
"#.#.......#.####.#.#", |
|
"####.###.#####...#.#", |
|
"#.##...###.....#.#.#", |
|
"#..##..#.#.#####.#.#", |
|
"##.##.##.#.#.#######", |
|
"#........#........G#", |
|
"####################", |
|
}; |
|
|
|
char tmp[21][21]; |
|
|
|
// fill image date by 0xff (white) |
|
void img_clear() { |
|
for (int i = 0; i < HEIGHT; i++) { |
|
for (int j = 0; j < WIDTH; j++) { |
|
buf[i][j][0] = buf[i][j][1] = buf[i][j][2] = 0xff; |
|
} |
|
} |
|
} |
|
|
|
// generate image file |
|
void img_write() { |
|
sprintf(fname, "img%04d.ppm", ++filecnt); |
|
FILE *f = fopen(fname, "wb"); |
|
if (f == NULL) { fprintf(stderr, "can't open %s\n", fname); exit(1); } |
|
fprintf(f, "P6\n%d %d\n255\n", WIDTH, HEIGHT); |
|
fwrite(buf, sizeof(buf), 1, f); |
|
fclose(f); |
|
} |
|
|
|
void img_putpixel(color c, int x, int y) { |
|
if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) { return; } |
|
buf[HEIGHT-y-1][x][0] = c.r; |
|
buf[HEIGHT-y-1][x][1] = c.g; |
|
buf[HEIGHT-y-1][x][2] = c.b; |
|
} |
|
|
|
void fill_square(color c, int x, int y) { |
|
for (int i = 0; i < 10; i++) { |
|
for (int j = 0; j < 10; j++) { |
|
img_putpixel(c, x+i, y+j); |
|
} |
|
} |
|
} |
|
|
|
void fill_s(int x, int y) { |
|
color c = {0, 0, 0}; |
|
char s[10][10] = { |
|
"..........", |
|
"...######.", |
|
"...######.", |
|
"##.##..##.", |
|
"##.##..##.", |
|
"##.##..##.", |
|
"##.##..##.", |
|
"#####.....", |
|
".####.....", |
|
"..........", |
|
}; |
|
for (int i = 0; i < 10; i++) { |
|
for (int j = 0; j < 10; j++) { |
|
if (s[i][j] == '#') { |
|
img_putpixel(c, x+i, y+j); |
|
} |
|
} |
|
} |
|
} |
|
|
|
void fill_g(int x, int y) { |
|
color c = {0, 0, 0}; |
|
char s[10][10] = { |
|
"..........", |
|
".########.", |
|
".##....##.", |
|
".##....##.", |
|
".##....##.", |
|
".##.##.##.", |
|
".#####.##.", |
|
".#####....", |
|
"....##....", |
|
}; |
|
for (int i = 0; i < 10; i++) { |
|
for (int j = 0; j < 10; j++) { |
|
if (s[i][j] == '#') { |
|
img_putpixel(c, x+i, y+j); |
|
} |
|
} |
|
} |
|
} |
|
|
|
void draw_maze() { |
|
color c = {0, 0, 0}; |
|
|
|
for (int i = 0; i < 20; i++) { |
|
for (int j = 0; j < 20; j++) { |
|
if (maze[i][j] == 'G') { |
|
fill_g(i*10, j*10); |
|
} |
|
else if (maze[i][j] == '#') { |
|
fill_square(c, i*10, j*10); |
|
} |
|
} |
|
} |
|
} |
|
|
|
void enqueue(Point c) { |
|
if (tail == 4000) { tail = 0; } |
|
que[tail++] = c; |
|
} |
|
|
|
Point dequeue() { |
|
if (head == 4000) { head = 0; } |
|
return que[head++]; |
|
} |
|
|
|
void copy_arr() { |
|
for (int i = 0; i < 20; i++) { |
|
for (int j = 0; j < 20; j++) { |
|
tmp[i][j] = maze[i][j]; |
|
} |
|
} |
|
} |
|
|
|
void dfs(int sx, int sy, int gx, int gy) { |
|
color c = {0, 255, 0}; |
|
fill_square(c, sx*10, sy*10); |
|
fill_s(10, 180); |
|
fill_g(180, 180); |
|
img_write(); |
|
tmp[sx][sy] = '#'; |
|
for (int i = 0; i < 4; i++) { |
|
int nx = sx + dx[i], ny = sy + dy[i]; |
|
// 範囲外かどうかの判定 |
|
if (nx < 0 || 19 < nx || ny < 0 || 19 < ny) { continue; } |
|
// 壁の判定 |
|
if (tmp[nx][ny] == '#') { continue; } |
|
// 未訪問かつ flag が立っていたら (ゴールが見つかっていなかったら) 進む |
|
else if (flag) { |
|
if (nx == gx && ny == gy) { flag = 0; } |
|
dfs(nx, ny, gx, gy); |
|
} |
|
} |
|
return ; |
|
} |
|
|
|
void bfs(int sx, int sy, int gx, int gy) { |
|
flag = 1; |
|
color c = {0, 255, 255}; |
|
fill_square(c, sx*10, sy*10); |
|
Point p; p.x = sx; p.y = sy; |
|
enqueue(p); |
|
fill_s(10, 180); |
|
fill_g(180, 180); |
|
img_write(); |
|
|
|
while (head != tail) { |
|
// Queue の先頭を取り出す |
|
p = dequeue(); |
|
int x = p.x, y = p.y; |
|
img_write(); |
|
// 移動を4方向にループ |
|
for (int i = 0; i < 4; i++) { |
|
// 移動した後の点を(nx, ny) とする |
|
int nx = x + dx[i], ny = y + dy[i]; |
|
p.x = nx; p.y = ny; |
|
// 範囲外かどうかの判定 |
|
if (nx < 0 || 19 < nx || ny < 0 || 19 < ny) { continue; } |
|
// 壁の判定 |
|
if (tmp[nx][ny] == '#') { continue; } |
|
|
|
else if (flag) { |
|
if (nx == gx && ny == gy) { flag = 0; } |
|
fill_square(c, nx*10, ny*10); |
|
tmp[nx][ny] = '#'; |
|
fill_s(10, 180); |
|
fill_g(180, 180); |
|
enqueue(p); |
|
img_write(); |
|
} |
|
else { |
|
return ; |
|
} |
|
} |
|
} |
|
} |
dfs.gif
bfs.gif
unite.gif