URAL1033[Labyrinth]

水题,BFS就行了。但是要注意一下起点和终点可能会不连通,我就是因为这一点WA了几次!


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-20


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


//using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      int N;


      vector<vector<char> > map;


      void bfs()


      {


           int answer=0;


           queue<pair<int,int> > q;


           vector<vector<bool> > inq(N,vector<bool>(N,false));


           #define go(dx,dy)\


           {\


                   int nexti=gi+(dx),nextj=gj+(dy);\


                   if ((nexti<N)\


                      &&(nexti>=0)\


                      &&(nextj<N)\


                      &&(nextj>=0)\


                      &&(!inq[nexti][nextj])\


                      &&(map[nexti][nextj]==’.’))\


                   {\


                     q.push(make_pair(nexti,nextj));\


                     inq[nexti][nextj]=true;\


                   }\


                   if ((nexti>=N)\


                       ||(nexti<0)\


                       ||(nextj>=N)\


                       ||(nextj<0)\


                       ||(map[nexti][nextj]==’#’))\


                      answer++;\


           }


           #define bfs_f(fi,fj)\


           if (!inq[fi][fj])\


           {\


              q.push(make_pair(fi,fj));\


              inq[fi][fj]=true;\


              while (!q.empty())\


              {\


                    int gi=q.front().first,\


                        gj=q.front().second;\


                    go(1,0);\


                    go(-1,0);\


                    go(0,1);\


                    go(0,-1);\


                    q.pop();\


              }\


           }


           bfs_f(0,0);


           bfs_f(N-1,N-1);


           #undef bfs_f


           #undef go


           answer-=4;


           answer*=3*3;


           cout<<answer<<endl;


      }


      public:


      Application()


      {


                    cin>>N;


                    map.resize(N,vector<char>(N));


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


                        for (int j=0;j<N;j++)


                            cin>>map[i][j];


      }


      int run()


      {


          bfs();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注