runtah: UVa 784 Maze Exploration

Sunday, December 25, 2016

UVa 784 Maze Exploration

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int dirs[10][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

char maze[100][100];
int color[100][100];

void dfs_visit(int x, int y)
{
 int i;
 color[x][y]=2;
 maze[x][y]=#;
 for (i=0 ; i<8 ; i++)
 {
 if (color[x+dirs[i][0]][y+dirs[i][1]]==0 && maze[x+dirs[i][0]][y+dirs[i][1]]!=X && maze[x+dirs[i][0]][y+dirs[i][1]]!=#)
 dfs_visit(x+dirs[i][0],y+dirs[i][1]);
 }
}

void dfs(int x, int y, int mh, int mw)
{
 int i, j;
 for (i=0 ; i<mh ; i++)
 for (j=0 ; j<mw ; j++)
 color[i][j] = 0;

 for (i=0 ; i<8 ; i++)
 {
 if (color[x+dirs[i][0]][y+dirs[i][1]]==0 && maze[x+dirs[i][0]][y+dirs[i][1]]!=X && maze[x+dirs[i][0]][y+dirs[i][1]]!=#)
 dfs_visit(x+dirs[i][0],y+dirs[i][1]);
 }
}


int end(char *p)
{
 int i;
 for (i=0 ; p[i] ; i++)
 {
 if (p[i]!=_) return 0;
 }
 return 1;
}
int seed(char *p)
{
 int i;
 for (i=0 ; p[i] ; i++)
 {
 if (p[i]==*) return i;
 }
 return -1;
}
int main()
{
 int test, maze_size, i, sx, sy;

 scanf("%d",&test);
 getchar();
 while (test--)
 {
 for (i=0 ; ; i++)
 {
 gets(maze[i]);

 if (end(maze[i]))
 break;
 }

 maze_size = i;

 for (i=0 ; i<maze_size ; i++)
 {
 if ((sy = seed(maze[i]))>=0)
 {
 sx = i;
 break;
 }
 }

 dfs(sx,sy,maze_size,80);

 for (i=0 ; i<=maze_size ; i++)
 puts(maze[i]);

 }
 return 0;
}
Go to link download