POJ3083 children of rhe candy corn

children of rhe candy corn"/>

POJ3083 children of rhe candy corn

题目大意：就是求最左优先，最右优先的路径长度(DFS不唯一),求最短路径(BFS唯一)

思路：代码TIE了，欲哭无泪，只好先放放，哪位大牛可以帮忙看看，怎么改进。。555

program:

#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h> 
using namespace std;
char map[41][41];
int flag[41][41];
int lm[4][2]={{0,-1},{-1,0},{1,0},{0,1}};
int rm[4][2]={{0,1},{-1,0},{1,0},{0,-1}};
int si,sj,ei,ej;
int m,n,cnt;
struct ditu
{
   char ch;
   int i,j;
   int d;      
}bfs_map[41][41];
int dfs_l(int i,int j)
{
// cout<<"ij  "<<i<<' '<<j<<" cnt "<<cnt<<endl;
  flag[i][j]=1;
  if(i==ei&&j==ej)  return cnt;
  for(int k=0;k<4;k++)
//注意这里<N，不能等于n ，机子发现不了的额，
//因为开的数组往往足够大啊
     if(i+lm[k][0]>=0&&i+lm[k][0]<n&&j+lm[k][1]>=0&&j+lm[k][1]<m&&map[i+lm[k][0]][j+lm[k][1]]!='#'&&!flag[i+lm[k][0]][j+lm[k][1]]) // 
      {           
        cnt++;
        if( dfs_l(i+lm[k][0],j+lm[k][1]))return cnt;
      }
  flag[i][j]= 0;
  cnt++;//返回的过程也加
  return 0;                 
}
int dfs_r(int i,int j)//
{
  //cout<<"ij  "<<i<<' '<<j<<" cnt "<<cnt<<endl; 
  flag[i][j]=1;
  if(i==ei&&j==ej)  return cnt;
  for(int k=0;k<4;k++)
     if(i+rm[k][0]>=0&&i+rm[k][0]<n&&j+rm[k][1]>=0&&j+rm[k][1]<m&&map[i+rm[k][0]][j+rm[k][1]]!='#'&&!flag[i+rm[k][0]][j+rm[k][1]]) // 
      {           
        cnt++;
        if( dfs_r(i+rm[k][0],j+rm[k][1]))return cnt; //一开始调用的竟然是左函数
      }
  flag[i][j]= 0;
  cnt++;
  return 0;                 
}
int bfs()
{
   queue<ditu>que;
   bfs_map[si][sj].d=1;
   que.push(bfs_map[si][sj]);
   flag[si][sj]=1;
   while(!que.empty())
   {
     ditu tmp=que.front();
     que.pop();
     for(int i=0;i<4;i++)
     {
       if(tmp.i+lm[i][0]>=0&&tmp.i+lm[i][0]<n&&tmp.j+lm[i][1]>=0&&tmp.j+lm[i][1]<m&&bfs_map[tmp.i+lm[i][0]][tmp.j+lm[i][1]].ch!='#'&&!flag[tmp.i+lm[i][0]][tmp.j+lm[i][1]])       
          {
             bfs_map[tmp.i+lm[i][0]][tmp.j+lm[i][1]].d=tmp.d+1;
             flag[tmp.i+lm[i][0]][tmp.j+lm[i][1]]=1;
             que.push(bfs_map[tmp.i+lm[i][0]][tmp.j+lm[i][1]]);
             if(tmp.i+lm[i][0]==ei&&tmp.j+lm[i][1]==ej)
               return  bfs_map[tmp.i+lm[i][0]][tmp.j+lm[i][1]].d;                                                                                                                                                              
          }    
     }                  
   } 
}

int main()
{
int test;
scanf("%d",&test);
while(test--)
{ 
   char tmp;
   scanf("%d%d",&m,&n);
//之所以会乱码，因为下面输入的时候没行末都有一个回车
//一开始的n，m在2个dfs都搞错顺序了，擦
//尼玛的m，n顺序搞错了，一开始的时候
//注意n是行，m是列
//我嚓，注意啊，dfs的数据不唯一啊
   memset(map,0,sizeof(map));
   memset(bfs_map,0,sizeof(bfs_map));// 
   for(int i=0;i<n;i++)
   {
//scanf("%c",&tmp);//or use getchar();
//把除了最后一行的回车都输进这里啊，鸟~~~
        getchar();
        for(int j=0;j<m;j++)
        {
         
          scanf("%c",&map[i][j]);
          bfs_map[i][j].ch=map[i][j];
          bfs_map[i][j].i=i;
          bfs_map[i][j].j=j;
          if(map[i][j]=='S')
          {  
             si=i;
             sj=j; 
          }
          else if(map[i][j]=='E')
          {
             ei=i;
             ej=j;   
          }     
        }
   }
/*   for(int i=0;i<n;i++)
   {
       
           for(int j=0;j<m;j++)
               printf("%c",map[i][j]);
           printf("\n"); 
   } */  
 //  cout<<"                 SiSj  "<<si<<' '<<sj<<"         eiej "<<ei<<' '<<ej<<endl;
   cnt=1;
   memset(flag,0,sizeof(flag));
   dfs_l(si,sj);  printf("%d ",cnt);//cout<<cnt<<' ';
   
   cnt=1;
   memset(flag,0,sizeof(flag));
   dfs_r(si,sj);  printf("%d ",cnt);//cout<<cnt<<' ';
  
   memset(flag,0,sizeof(flag));
   printf("%d\n",bfs());//cout<<bfs()<<endl;
   
      
}   
system("pause");
return 0;}