zoj_2210.txt

zoj 2210的代码和方法说明,个人原创

zoj 22102009-03-31 21:33花了50ms,搞不懂那些0ms的是怎么弄的

#include<iostream>
#include<queue>
using namespace std;
char ch[10][10];
int maze[10][10],n,m,t,maxf=0x0fffffff,sx,sy,ax,ay,step[10][10],wal;
int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int visit[10][10];
int dfs(int x,int y,int stepx)//判断从x,y开始的时候,已经走了stepx,这种情况是否可以到达目标点
{   
int x1,y1,k;
if(stepx==t&&maze[x][y]==0)//如果到了,并且走了t次,返回1
   return 1;
k=t-stepx-1;//剩下还需要多少次
for(int i=0;i<4;i++)
{
   x1=x+move[i][0];
   y1=y+move[i][1];
   if(visit[x1][y1]==0&&k>=maze[x1][y1]&&k%2==step[x1][y1])//剩下的步数的奇偶性必须和x1,y1到目标点的坐标差的和的绝对值
                                  //奇偶性相同,并且如果k小于x1,y1到目标点的最小值,那么根本不用搜

   { if(maze[x1][y1]==0)
    {
     if(stepx+1==t)
      return 1;

     continue;

    }
    visit[x1][y1]=1;//标记访问过了
   
    if(dfs(x1,y1,stepx+1))
     return 1;
    visit[x1][y1]=0;
   }
}
return 0;
}
   


class ty
{
public:
int x,y,step;
};
int main()
{
while(scanf("%d %d %d",&n,&m,&t)&&n)
{ wal=0;
   int i,j,k;
   for(i=1;i<=n;i++)
    scanf("%s",ch[i]+1);
   memset(maze,-1,sizeof(maze));//maze[x][y]代表x,y到目标点的最小步数
   for(j=0;j<=m+1;j++)
    maze[n+1][j]=maze[0][j]=maxf;
   for(j=1;j<=n;j++)
    maze[j][0]=maze[j][m+1]=maxf;//把边界点到目标点的距离改为无限
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
     if(ch[i][j]=='X')
     { maze[i][j]=maxf;
     wal++;//墙的数目
     }
     else if(ch[i][j]=='S')
     {
      sx=i;
      sy=j;
     }
     else if(ch[i][j]=='D')
     {
      ax=i;
      ay=j;
      maze[i][j]=0;
     }
    }
    queue<ty> list;
    ty tem,pp;
    tem.x=ax;
    tem.y=ay;
    step[ax][ay]=0;//step代表x,y到目标点的横坐标差的绝对值,纵坐标差的绝对值的总和的奇偶性
    for(i=0;i<4;i++)
    {
     tem.x=ax+move[i][0];
     tem.y=ay+move[i][1];
     tem.step=1;
     if(maze[tem.x][tem.y]==-1)
     { maze[tem.x][tem.y]=1;
step[tem.x][tem.y]=(abs(tem.x-ax)+abs(tem.y-ay))%2;
       list.push(tem);
     }
    }
    while(list.size())//广搜计算矩阵中每点到目标点的最小距离
    {
     pp=list.front();
     tem.step=pp.step+1;
     for(i=0;i<4;i++)
    {
     tem.x=pp.x+move[i][0];
     tem.y=pp.y+move[i][1];
                
     if(maze[tem.x][tem.y]==-1)
     { maze[tem.x][tem.y]=pp.step+1;
       step[tem.x][tem.y]=(abs(tem.x-ax)+abs(tem.y-ay))%2;
       list.push(tem);
     }
    }
     list.pop();
     
    }
  
    for(i=0;i<10;i++)
     for(j=0;j<10;j++)
      if(maze[i][j]==-1)
       maze[i][j]=maxf;
    if(maze[sx][sy]>t||n*m-wal<=t)
    {
    cout<<"NO\n";
     continue;
    }
   // if(maze[sx][sy]==0&&t==0)
   // {
   //   cout<<"YES\n";
   //   continue;
   // }
          memset(visit,0,sizeof(visit));
    visit[sx][sy]=1;
    if(dfs(sx,sy,0))
              cout<<"YES\n";
    else
              cout<<"NO\n";
    }
return 0;
}