URAL1006[Square frames]

一道巨麻烦的题,但是没有多少算法上的价值。


枚举x,y,a一直找,如果找到(即每边都没有错误的点,即,不是该是的图案,又不是被覆盖了),就输出,并覆盖所有边框上的点。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-11


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <vector>


using std::vector;


#include <string>


//using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <cassert>


//using std::assert;


 


class Application


{


      typedef unsigned char uc;


      static const int W=50,H=20;


      static const uc LU=218,//Left upper corner


                      RU=191,//Right upper corner


                      LB=192,//Left bottom corner


                      RB=217,//Right bottom corner


                      VE=179,//Vertical (left and right) border line


                      HO=196,//Horizontal (top and bottom) border line


                      DO=46,//Dot


                      CO=0;//Cover


      uc pic[H][W];


      public:


      Application()


      {


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


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


                            cin>>pic[i][j];


      }


      int run()


      {


          bool update=true;


          stack<pair<pair<int,int>,int> > answer;


          while (update)


          {


                /*


                cout<<“updating…”<<endl;


                for (int x=0;x<H;x++)


                {


                    for (int y=0;y<W;y++)


                    {


                        switch(pic[x][y])


                        {


                                         case LU:cout<<‘/’;break;


                                         case RU:cout<<‘\\’;break;


                                         case LB:cout<<‘\\’;break;


                                         case RB:cout<<‘/’;break;


                                         case VE:cout<<‘|’;break;


                                         case HO:cout<<‘-‘;break;


                                         case DO:cout<<‘.’;break;


                                         case CO:cout<<‘ ‘;break;


                        }


                    }


                    cout<<endl;


                }


                */


                update=false;


                for (int x=0;x<H;x++)


                    for (int y=0;y<W;y++)


                        if (pic[x][y]==CO||pic[x][y]==LU)


                           for (int a=2;a<=H;a++)


                               if ((pic[x+a-1][y]==CO||pic[x+a-1][y]==LB)


                                  &&(pic[x][y+a-1]==CO||pic[x][y+a-1]==RU)


                                  &&(pic[x+a-1][y+a-1]==CO||pic[x+a-1][y+a-1]==RB))


                               {


                                  #define impossibleHO(x,y) ((x>=H)or(y>=W)or((pic[x][y]!=CO)&&(pic[x][y]!=HO)))


                                  #define impossibleVE(x,y) ((x>=H)or(y>=W)or((pic[x][y]!=CO)&&(pic[x][y]!=VE)))


                                  bool ispossible=true;


                                  bool L=false,R=false,U=false,B=false;


                                 


                                  if (pic[x][y]==LU) L=U=true;


                                  if (pic[x+a-1][y]==LB) L=B=true;


                                  if (pic[x][y+a-1]==RU) R=U=true;


                                  if (pic[x+a-1][y+a-1]==RB) R=B=true;


                                 


                                  for (int i=1;i<a-1;i++)


                                  {


                                      if (impossibleHO(x,y+i)


                                         ||impossibleHO(x+a-1,y+i)


                                         ||impossibleVE(x+i,y)


                                         ||impossibleVE(x+i,y+a-1))


                                      {


                                         ispossible=false;


                                         break;


                                      }


                                      if (pic[x][y+i]==HO) U=true;


                                      if (pic[x+a-1][y+i]==HO) B=true;


                                      if (pic[x+i][y]==VE) L=true;


                                      if (pic[x+i][y+a-1]==VE) R=true;


                                  }


                                  #define cover(x,y) pic[x][y]=CO;


                                  if (ispossible&&(L||R||U||B))


                                  {


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


                                     {


                                         cover(x,y+i);


                                         cover(x+a-1,y+i);


                                         cover(x+i,y);


                                         cover(x+i,y+a-1);


                                     }


                                     update=true;


                                     answer.push(make_pair(make_pair(y,x),a));


                                     //cout<<y<<” “<<x<<” “<<a<<endl;


                                  }


                                  #undef impossibleHO


                                  #undef impossibleVE


                                  #undef cover


                               }


          }


          cout<<answer.size()<<endl;


          while (!answer.empty())


          {


                cout<<answer.top().first.first<<” “


                    <<answer.top().first.second<<” “


                    <<answer.top().second<<endl;


                answer.pop();


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


留下评论

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