http://acm.hdu.edu.cn/showproblem.php?pid=1728

这两道题花了一下午的时候调试，因为以前做过类似的题，但是判断方向的方法是错的,一直没发现啊,真无语。

每个状态除了坐标外还需要记录步数,和方向。还要注意输入格式。

并且每一个点并不是走过了就不能在走,只要到达这个点的时候转向次数少的就可以更新这个点，可以等于。千万注意这个坑。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int n,m,k; 6 int dir[4][2]={
   {
   0,1},{
   1,0},{
   0,-1},{-1,0}}; 7 char mp[110][110]; 8 int used[110][110]; 9 struct point10 {11     int x,y,d,time;12     bool operator < (const point a) const13     {14         return time>a.time;15     }16 };17 void bfs(int x1,int y1,int x2,int y2)18 {19     //printf("%d %d %d %d\n",x1,y1,x2,y2);20     for(int i=0;i<=n;i++)21         for(int j=0;j<=m;j++) used[i][j]=1<<29;22     priority_queue
        
         que;23     point s;24     s.x=x1,s.y=y1,s.d=-1,s.time=0;25     que.push(s);26     used[s.x][s.y]=0;27     while(!que.empty())28     {29         point e=que.top(); que.pop();30         printf("%d %d %d\n",e.x,e.y,e.time);31         if(e.time>k) continue;32         if(e.x==x2&&e.y==y2) {printf("yes\n");return;}33         for(int i=0;i<4;i++)34         {35             s.x=e.x+dir[i][0];36             s.y=e.y+dir[i][1];37             if(s.x<0||s.x>=n||s.y<0||s.y>=m||mp[s.x][s.y]=='*') continue;38             s.d=i;39             if(s.d!=e.d&&e.d!=-1)  //转向次数加1   并且保证不会往回走构成死循环40             {41                 s.time=e.time+1;42             }43             else s.time=e.time;44             if(s.time<=used[s.x][s.y]&&s.time<=k) //注意45             {46                 used[s.x][s.y]=s.time;47                 que.push(s);48             }49         }50     }51     printf("no\n");52 }53 54 int main()55 {56     freopen("a.txt","r",stdin);57     int t,x1,y1,x2,y2;58     scanf("%d",&t);59     while(t--)60     {61         scanf("%d%d",&n,&m);62         getchar();63         for(int i=0;i
        
       
      
     

知道写bfs了 换成dfs还是挺容易的。

并且bfs是1400ms,dfs只有31ms。

#include 
     
      #include 
      
       char mp[110][110];int n,m,k;int dir[4][2]={
   {-1,0},{
   1,0},{
   0,1},{
   0,-1}};int x2,y2;bool flag;int vis[110][110];void dfs(int x,int y,int d,int step){    //printf("%d %d %d %d\n",x,y,d,step);    if(flag) return;    if(x==x2&&y==y2&&step<=k)    {        flag=1;        printf("yes\n");        return;    }    for(int i=0;i<4;i++)    {        int xx=x+dir[i][0];        int yy=y+dir[i][1];        int dd=i;        if(xx>=0&&xx
       
        =0&&yy
       
      
     

 

http://acm.hdu.edu.cn/showproblem.php?pid=1175

这个题的坑点在于只能两个端点是非0数,不能经过其他的数字。

思路是一样的。

#include 
     
      #include 
      
       #include 
       
        using namespace std;int n,m;int dir[4][2]={
   {
   0,1},{
   1,0},{
   0,-1},{-1,0}};int mp[1010][1010];int used[1010][1010];struct point{    int x,y,d,time;    bool operator < (const point a) const    {        return time>a.time;    }};point t;bool bfs(point s){    for(int i=0;i<=n;i++)        for(int j=0;j<=m;j++) used[i][j]=1<<29;    priority_queue
        
         que;    que.push(s);    used[s.x][s.y]=0;    while(!que.empty())    {        point e=que.top(); que.pop();        if(e.x==t.x&&e.y==t.y) return true;        for(int i=0;i<4;i++)        {            s.x=e.x+dir[i][0];            s.y=e.y+dir[i][1];            s.d=i;            if(s.x<1||s.x>n||s.y<1||s.y>m) continue;            if(mp[s.x][s.y]!=0&&(s.x!=t.x||s.y!=t.y)) continue;  //注意别逻辑别写错了            //printf("%d %d %d\n",s.x,s.y,s.time);            if(s.d!=e.d&&e.d!=-1) s.time=e.time+1;            else s.time=e.time;            if(s.time<=used[s.x][s.y]&&s.time<=2)            {                used[s.x][s.y]=s.time;                que.push(s);            }        }    }    return false;}int main(){   //freopen("a.txt","r",stdin);    int q,x1,y1,x2,y2;    while(~scanf("%d%d",&n,&m))    {        if(n==0&&m==0) break;        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]);        scanf("%d",&q);        while(q--)        {            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);            if(!mp[x1][y1]||mp[x1][y1]!=mp[x2][y2]) printf("NO\n");            else            {                point s;                s.x=x1,s.y=y1,s.d=-1,s.time=0;                t.x=x2,t.y=y2;                if(bfs(s)) printf("YES\n");                else printf("NO\n");            }        }    }    return 0;}