哇哦~这就是我

This is my way ~
<2008年3月>
2425262728291
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

  • 随笔 - 10
  • 文章 - 0
  • 评论 - 2
  • 引用 - 0

常用链接

留言簿(1)

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

push!

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
struct NODE
{
 int p_x,p_y,step,c_x,c_y,d;
};
queue<NODE> que;
const int MAXN = 100;
bool p[MAXN][MAXN][4],c[MAXN][MAXN];
int map[MAXN][MAXN];
int mv[4][2]={-1,0,0,1,1,0,0,-1},p_sm,p_sn,c_sm,c_sn,m,n;
void init ( )
{
 memset(p,false,sizeof(p));
 for ( int i=0 ; i<m ; i++ )
  for ( int j=0 ; j<n ; j++ )
  {
   scanf("%d",&map[i][j]);
   if ( map[i][j]==4 )
    p_sm=i,p_sn=j;
   else
    if ( map[i][j]==2 )
     c_sm=i,c_sn=j;
  }
}
int bfs ( )
{
 NODE temp,go;
 int i;
 temp.p_x = p_sm;
 temp.p_y = p_sn;
 temp.c_x = c_sm;
 temp.c_y = c_sn;
 temp.step = 0;
 temp.d=0;
 for ( i=0 ; i<4 ; i++ )
 {
  p[p_sm][p_sn][i]=true;
  temp.d=i;
  que.push(temp);
 }
 c[c_sm][c_sn]=true;
 while ( !que.empty () )
 {
  NODE head=que.front();
  que.pop() ;
  for ( i=0 ; i<4 ; i++ )
  {
   int tm=head.p_x+mv[i][0] , tn=head.p_y+mv[i][1] ;
   if ( tm>=0 && tm<m && tn>=0 && tn<n && !p[tm][tn][i] && i!=(head.d+2)%4 && map[tm][tn]!=1 )
   {
    double t=sqrt( (double)( (tm-head.c_x)*(tm-head.c_x) ) +(double)( (tn-head.c_y)*(tn-head.c_y) ));
    if ( t <= sqrt(2.0) && t>0 )
    {
     go=head;
     go.p_x = tm;
     go.p_y = tn;
     go.step ++ ;
     go.d=i;
     p[tm][tn][i]=true;
     que.push(go);
    }
    else
    {
     int tmm=tm+mv[i][0] , tnn=tn+mv[i][1];
     if ( t==0 && tmm>=0 && tmm<m && tnn>=0 && tnn<n && map[tmm][tnn]!=1 && !c[tmm][tnn] )
     {
      go.c_x = tmm ;
      go.c_y = tnn ;
      go.p_x = tm;
      go.d=i;
      go.p_y = tn;
      go.step = head.step+1;
      if ( map[tmm][tnn]==3 )
       return go.step ;
      c[tmm][tnn]=true;
      p[tm][tn][i]=true;
      que.push(go);
     }
    }
   }
  }
 }
 return -1;
}
int main ( )
{
 while ( scanf("%d%d",&n,&m)!=EOF )
 {
  init();
  printf("%d\n",bfs());
 // que.

 }
}

posted on 2008-05-28 01:36 chinaeli 阅读(90) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理