NYOJ999 师傅又被妖怪抓走了

只记得当下的眼疼 , ok 各种数据也试了 , 就是 他娘的不对 , 我也是醉了 . 也是日了最野的狗

附上日了哮天犬的代码 , 这个题 先放放, 一段时间后再试试 , 明天开始状态压缩吧 .为期两天

今天早上 一眼就看出来了 代码的  漏洞 , 以后应该 自己想不出来的代码 让别人看看   ,   互相交换着看看

预处理 + 两重广搜

 #include<stdio.h>

 #include<string.h>

 #include<math.h>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<set>

 #include<stack>

 #include<string>

 #include<sstream>

 #include<map>

 #include<cctype>

 using namespace std;

 int n,m,b[][]={,-,,,-,,,},minn,visited[][],vis[][];

 char a[][];

 struct monkey

 {

     int x,y,step;

 };

 queue<monkey>Q;

 void pretreatment(int x,int y,char b,char c)   //坐标 和 该名称  和  另一人名称

 {

     for(int i=x+;i<m&&a[y][i]!='X'&&a[y][i]!=c;i++)

         a[y][i]=(a[y][i]=='d'?'O':b+);

     for(int i=x-;i>=&&a[y][i]!='X'&&a[y][i]!=c;i--)

         a[y][i]=(a[y][i]=='d'?'O':b+);

     for(int i=y+;i<n&&a[i][x]!='X'&&a[i][x]!=c;i++)

         a[i][x]=(a[i][x]=='d'?'O':b+);

     for(int i=y-;i>=&&a[i][x]!='X'&&a[i][x]!=c;i--)

         a[i][x]=(a[i][x]=='d'?'O':b+);

 }

 queue<monkey>W;

 void BFSMORE(int x,int y,int step,char c)

 {

     monkey q={x,y,step};

     W.push(q);

     while(!W.empty())

     {

         monkey e=W.front();

         W.pop();

         for(int i=;i<;i++)

         {

             q.x=e.x+b[i][],q.y=e.y+b[i][];

             if(a[q.y][q.x]!='X'&&a[q.y][q.x]!='D'&&a[q.y][q.x]!='E'&&q.x>=&&q.x<m&&q.y>=&&q.y<n&&!vis[q.y][q.x])

             {

                 vis[q.y][q.x]=;

                 q.step=e.step+;

                 W.push(q);

                 if(a[q.y][q.x]==c||a[q.y][q.x]=='O')

                 {

                     minn=minn>q.step?q.step:minn;

                     while(!W.empty())

                         W.pop();

                     break;

                 }

             }

         }

     }

 }

 void BFS(int x,int y)

 {

     monkey q={x,y,};

     if(a[y][x]=='O')

     {

         minn=;

         return ;

     }

     if(a[y][x]=='d')

     {

         memset(vis,,sizeof(vis));

         BFSMORE(x,y,,'e');

     }

     if(a[y][x]=='e')

     {

         memset(vis,,sizeof(vis));

         BFSMORE(x,y,,'d');

     }

     Q.push(q);

     while(!Q.empty())

     {

         monkey e=Q.front();

         Q.pop();

         for(int i=;i<;i++)

         {

             q.x=e.x+b[i][],q.y=e.y+b[i][];

             if(a[q.y][q.x]!='X'&&a[q.y][q.x]!='D'&&a[q.y][q.x]!='E'&&q.x>=&&q.x<m&&q.y>=&&q.y<n&&!visited[q.y][q.x])

             {

                 q.step=e.step+;

                 Q.push(q);

                 visited[q.y][q.x]=;

                 if(a[q.y][q.x]=='O')

                 {

                     minn=minn>q.step?q.step:minn;

                 }

                 if(a[q.y][q.x]=='d')

                 {

                     memset(vis,,sizeof(vis));

                     BFSMORE(q.x,q.y,q.step,'e');

                 }

                 if(a[q.y][q.x]=='e')

                 {

                     memset(vis,,sizeof(vis));

                     BFSMORE(q.x,q.y,q.step,'d');

                 }

             }

         }

     }

 }

 int main()

 {

     int sx,sy,dx,dy,ex,ey,t,count1=;

     while(scanf("%d%d%d",&n,&m,&t)!=EOF)

     {

         minn=t+;

         for(int i=;i<n;i++)

         {

             for(int j=;j<m;j++)

             {

                 scanf(" %c",&a[i][j]);

                 if(a[i][j]=='S')

                 {

                     sx=j;

                     sy=i;

                 }

                 if(a[i][j]=='D')

                 {

                     dx=j;

                     dy=i;

                 }

                 if(a[i][j]=='E')

                 {

                     ex=j;

                     ey=i;

                 }

             }

         }

         pretreatment(dx,dy,'D','E');

         pretreatment(ex,ey,'E','D');

         memset(visited,,sizeof(visited));

         visited[sy][sx]=;

         BFS(sx,sy);

         printf("Case %d:\n",++count1);

         if(minn<=t)

             printf("%d\n",minn);

         else

             printf("-1\n");

     }

     return ;

 }