POJ 1321解题报告

1、
对于这道题目,刚开始有点发懵.
一般的棋盘都是规则的,可这个是不规则的,刚开始看确实有点懵懵的感觉.我这个人呀,说不来,很没有信心的那种,一看是新情景,就心里面直打鼓.
后来看了看测试用例,呵呵,实际上,不规则和规则的差不太多啊!!,最关键的是处理好剪枝技巧!
好的剪枝,可以节省很多时间的.
不过在这道题目上,我并没有剪很多枝,但第一个for循环,自我感觉很漂亮!

          for(int i=row;i<=(row+Row-Count)&&i<=Row;i++)

因为这个东西,则可以少很多搜索,提交后0ms,呵呵,这时我做搜索题目以来的第一次0ms,鼓掌ing...
2、
这道题目第二点值得学习的是,在搜索中利用了两个for循环,并很恰当的利用了矩阵的第0行.鼓掌ing...

Source Code

Problem: 1321		User: omycle
Memory: 252K		Time: 0MS
Language: C++		Result: Accepted

• Source Code
  

  #include<iostream>
  using namespace std;
  /*typedef struct
  {
   int row;
   int col;
  }Zoufa;*/
  //Zoufa zf[0x00ffffff];
  int Layout=0;
  int Col=0;
  int Row=0;
  int **mg;
  //int mg[7][7];
  /*
  ={0,0,0,0,0,0,0,
  1,-1,-1,-1,1,-1,-1,\
  1,-1,-1,-1,-1,1,-1,\
  1,-1,-1,1,-1,-1,-1,\
  1,-1,1,-1,-1,-1,-1,\
  1,1,-1,-1,-1,-1,-1,\
  1,1,-1,-1,-1,-1,-1};
  bool flag[7][7]; //default为false 
  */
  /*
  第一行用作标志，该列被使用了
  第一列存放该行中可以有多少个位置放棋子 
  */
  int Count;//放k个棋子 default=4
  void Dfs(int row,int k)//走到哪一行了,该放哪一个棋子了 
  {
  for(int i=row;i<=(row+Row-Count)&&i<=Row;i++)
  {
  for(int j=1;j<=Col;j++)//在每一列可以放吗？ 
  {
  if(0==mg[0][j]&&1==mg[i][j])
  {
  if(k==Count)
  {
  /* zf[k].row=i;
       zf[k].col=j;
       for(int i_=1;i_<=Count;i_++)
       { 
        printf("(%d,%d) ",zf[i_].row,zf[i_].col);
   
       }
       printf("\n");
      */
       Layout++;//走法加一 
  continue;
  }
      mg[0][j]=1;//标识被用过 
  // zf[k].row=i;
  // zf[k].col=j;
  Dfs(i+1,k+1);
      mg[0][j]=0;
  }
  }
  }
  }
  void Print()
  {
  printf("%d",Layout);
  }
  int main()
  {
  int n=0;
  while(1)
  {
    Layout=0;
    cin>>n>>Count;//多少行列，多少k
  if(n==-1&&Count==-1)
  break;
    mg=(int * *)malloc((n+1)*sizeof(int *));
    mg[0]=(int *)malloc((n+1)*sizeof(int));
  int i;
  for(i=1;i<=n;i++)
     mg[0][i]=0;
  for(i=1;i<=n;i++)
  {
     mg[i]=(int *)malloc((n+1)*sizeof(int));
  for(int j=1;j<=n;j++)
  {
  char a;
      cin>>a;
  if(a=='.')
       mg[i][j]=-1;
  else
       mg[i][j]=1;
  }
  }
  /* for(i=1;i<=n;i++)
    { for(int j=1;j<=n;j++)
      cout<<mg[i][j]<<' ';
    printf("\n");
    }
   
   */
  //Count=4;
    Col=n;
    Row=n;
  Dfs(1,1);
  Print();
  printf("\n");
  free(mg);
  }
  return 0;
  }