风之心语
记录我们的点点滴滴~
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
« 上一篇: zoJ 1906 欧拉函数求素数个数 下一篇: ZOJ 1733 经典DP »
Spirit @ 2005-07-29 16:43

#include

const int MAX = 7;
char map[MAX][MAX];
int row;
int col;
int Visited[MAX][MAX];
int total;
int lamp;
int count;
struct Dir
{
int off_x;
int off_y;
}dir[4];

void dirGen()
{
dir[0].off_x = 0; dir[0].off_y = 1;
dir[1].off_x = 1; dir[1].off_y = 0;
dir[2].off_x = -1; dir[2].off_y = 0;
dir[3].off_x = 0; dir[3].off_y = -1;
}
void init()
{
int i, j;
lamp = 0;
for( i = 0; i < MAX; i ++ )
 for( j = 0; j < MAX; j ++ )
 {
  map[j] = '{post.content}';
  Visited[j] = 0;
 }
}
void DFS( int x, int y, int num )//num是访问过的总的种子数
{
int i;
int new_x, new_y;

if( num == total )
{
 lamp = 1;
 return ;
}
else
{
 for( i = 0; i < 4; i ++ )
 {
  new_x = x + dir.off_x;
  new_y = y + dir.off_y;

  if( new_x >= 0 && new_x < row //没出界
   && new_y >= 0 && new_y < col
   && Visited[new_x][new_y] == 0//保证没访问过
   && map[new_x][new_y] != 'S' )//保证不是石头
  {
   Visited[new_x][new_y] = 1;
   DFS( new_x, new_y, num + 1 );
  // Visited[new_x][new_y] = 0;
  }
 }
}
}
int main()
{
int i, j;
dirGen();
while( scanf( "%d %d", &row, &col ) != EOF )
{
 count = 0;
 if( row == 0 && col == 0 )
  break;
 init();
 total = 0;
 gets( map[0] );
 for( i = 0; i < row; i ++ )
  gets( map );
 for( i = 0; i < row; i ++ )
  for( j = 0; j < col; j ++ )
  {
   if( map[j] == '.' )
    total ++;//total 是总的点数
  }
 DFS( 0, 0, 1 );
 if( lamp == 1 )
  printf("YES\n");
 else
  printf("NO\n");
}
return 0;
}


评论 / 个人网页 / 扔小纸条
*昵称

已经注册过? 请登录

Email
网址
*评论
 


 
分类
· 所有网志 (16)
· 游戏世界 (2)
· ACM-ICPC (8)
· 心情文章 (4)
· 音乐天堂 (1)
· 杂感 (1)
链接
· 我的歪酷
站内搜索
订阅 RSS
0002156
歪酷博客