《挑战程序设计竞赛》2.1最基础的穷竭搜索

2021-02-13网站开发发消息

深度优先搜索：

第一题：POJ1979Red and Black http://poj.org/problem?id=1979

题意：在一个W*H的矩形中，每个单位的格子是红色或是黑色的，'@'是初始位置，'.'是黑色的格子'，#'是红色的格子，给出地图，要求输出从初始位置通过黑色的格子可以到达的所有位置的总数。

代码：
#includeiostream
using namespace std;
char map[21][21];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int sum,W,H;
void DFS(int x,int y)
{
    ++sum;
    map[x][y]='@';
    int newx,newy;
    for(int i=0;i4;i++)
    {
        newx=x+dir[i][0];
        newy=y+dir[i][1];
        if(newx=0newxHnewy=0newyWmap[newx][newy]=='.')
            DFS(newx,newy);
    }
}
int main()
{
  int x,y;
  while(cinWHW!=0H!=0){
      sum=0;
  for(int i=0;iH;i++)
    for(int j=0;jW;j++)
    {
     cinmap[i][j];
     if(map[i][j]=='@')
     {
       x=i;y=j;
     }
    }
    DFS(x,y);
    coutsumendl;
  }
}

第二题：AOJ 0118 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118

题意：在H * W的矩形果园里有苹果、梨、蜜柑三种果树，相邻（上下左右）的同种果树属于同一个区域，给出果园的果树分布，求总共有多少个区域。（原题的样图中苹果为リ，梨为カ，蜜柑为ミ，图中共10个区域）输入：多组数据，每组数据第一行为两个整数H、W（H = 100, W = 100）， H =0 且 W = 0代表输入结束。以下H行W列表示果园的果树分布，苹果是@，梨是#，蜜柑是*。输出：对于每组数据，输出其区域的个数。

代码：
#includeiostream
using namespace std;
int W,H;
char map[101][101];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void DFS(int x,int y,char ch)
{
    map[x][y]='.';
    int newx,newy;
    for(int i=0;i4;i++)
    {
      newx=dir[i][0]+x;
      newy=dir[i][1]+y;
      if(newx=0newxHnewy=0newyWmap[newx][newy]==ch)
        DFS(newx,newy,ch);
    }

}
int main()
{
    int count;
    char ch;
  while(cinHWW!=0H!=0)
  {
      count=0;
    for(int i=0;iH;i++)
        for(int j=0;jW;j++)
      cinmap[i][j];
      
    for(int i=0;iH;i++)
      for(int j=0;jW;j++)
      {
          ch=map[i][j];
         if(ch!='.')
         {
             count++;
             DFS(i,j,ch);
         }
      }
      coutcountendl;
  }

}

第三题： AOJ 0033 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
题意：（见图）有一个形似央视大楼的筒，从 A 口可以放球，放进去的球可通过挡板 DE 使其掉进 B 裤管或 C 裤管里，现有带 1-10 标号的球按给定顺序从 A 口放入，问是否有一种控制挡板的策略可以使 B 裤管和 C 裤管中的球从下往上标号递增。输入：第一行输入数据组数 N 。接下来 N 行为 N 组具体数据，每组数据中有 10 个整数，代表球的放入顺序。输出：对于每组数据，若策略存在，输出 YES ；若不存在，输出 NO 。

代码：
#includeiostream
#includememory.h
using namespace std;
int arr[10],used[10];
void DFS(int pre,int cur)
{
   if(cur10arr[pre]arr[cur])
   {
       used[cur]=1;
       DFS(cur,cur+1);
   }
   else if(cur10arr[pre]=arr[cur])
       DFS(pre,cur+1);
}
int main()
{
   int T,pre;
   bool judge;
   cinT;
   while(T--)
   {
     for(int i=0;i10;i++)
         cinarr[i];
     for(int i=0;i10;i++)
     {
         memset(used,0,sizeof(used));
         used[i]=1;
         DFS(i,i+1);
         judge=false;
         pre=0;
         for(int j=0;j10;j++)
            if(used[j]==0)
                if(pre=arr[j])
            {
                judge=true;
                break;
            }else pre=arr[j];
         if(!judge)
         {
             cout"YES"endl;
             break;
         }
     }
     if(judge)cout"NO"endl;
   }

}

第四题： POJ3009Curling 2.0 http://poj.org/problem?id=3009
题意：就是要求把一个冰壶从起点 2 用最少的步数移动到终点 3。其中 0 为移动区域， 1 为石头区域，冰壶一旦想着某个方向运动就不会停止，也不会改变方向（想想冰壶在冰上滑动），除非冰壶撞到石头 1 或者到达终点 3。
注意的是：冰壶撞到石头后，冰壶会停在石头前面，此时（静止状态）才允许改变冰壶的运动方向，而该块石头会破裂，石头所在的区域由 1 变为 0. 也就是说，冰壶撞到石头后，并不会取代石头的位置。终点是一个摩擦力很大的区域，冰壶若到达终点 3 ，就会停止在终点的位置不再移动。

代码：
#includeiostream
using namespace std;
int W,H,arr[21][21];
int Min,dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void DFS(int x,int y,int step)
{
    if(step10)
        return;
    int newx,newy;
    for(int i=0;i4;i++)
    {
      newx=x+dir[i][0];
      newy=y+dir[i][1];
      if(!(newx=0newxHnewy=0newyW)||arr[newx][newy]==1)
          continue;
        while(arr[newx][newy]==0)
        {
           newx+=dir[i][0];
           newy+=dir[i][1];
        }
    //  coutnewx" "newyendl;
      if(newx=0newxHnewy=0newyW)
      {
          if(arr[newx][newy]==1)
          {
             arr[newx][newy]=0;
             newx-=dir[i][0];
             newy-=dir[i][1];
             DFS(newx,newy,step+1);
             arr[newx+dir[i][0]][newy+dir[i][1]]=1;
          }
          else if(arr[newx][newy]==3)
          {
            Min=Minstep?step:Min;
          }
      }
    }
}
int main()
{
    int startx,starty;
  while(cinWHW!=0H!=0)
  {
      Min=11;
    for(int i=0;iH;i++)
      for(int j=0;jW;j++)
      {
         cinarr[i][j];
         if(arr[i][j]==2)
         {
           arr[i][j]=0;
           startx=i;starty=j;
         }
      }
    DFS(startx,starty,1);
    if(Min10)
        cout"-1"endl;
    else coutMinendl;
  }
}

技术程序设计