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

深度优先搜索:

第一题: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个区域)  输入:多组数据,每组数据第一行为两个整数HWH = 100, W = 100), H =0 且 W = 0代表输入结束。以下HW列表示果园的果树分布, 苹果是@,梨是#, 蜜柑是*。  输出:对于每组数据,输出其区域的个数。

代码:
#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 为石头区域,冰壶一旦想着某个方向运动就不会停止,也不会改变方向(想想冰壶在冰上滑动),除非冰壶撞到石头 或者 到达终点  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;
  }
}




最新回复(0)
/jishuN1MxZkOVDYS91GRY1rvnOGERFCxmJ5c53gIcsw_3D_3D4858273
8 简首页