大意 黑白棋 翻1个周围4个跟着翻 问最少几步能全部翻成同1个颜色(不行输出不行)
纯粹的深搜 WRONG满久在到最后1个b[4][4]的时候没判断好浪费了很久时间
比较有收获的是了解了深搜的流程 练习了下
对输入的B W转化为0和1 用位运算解决翻页省了满多步骤 个人觉得还满巧妙的嘿嘿
#include<stdio.h>
#include<stdlib.h>     
char a[100][100],b[100][100];
int m=0,min;
void fan(int x,int y)
{
 b[x][y-1]=b[x][y-1]^1;
 b[x+1][y]=b[x+1][y]^1;
 b[x][y+1]=b[x][y+1]^1; 
 b[x][y]=b[x][y]^1;
 b[x-1][y]=b[x-1][y]^1;
}
void bfs(int x,int y)
{
 int i,j,h=0;
 for(i=1;i<=4;i++)
 {
  for(j=1;j<=4;j++)
  {
   if(b[i][j]!=b[1][1])
   { 
    h=1;
    break;
   }
  }
  if(h==1)
  {
   h=0;
   break;
  }
 }
 if(i==5&&j==5)
 {
  if(min>m||min==-1)
  {
   min=m;
   return ;
  }
 }
 if(y==4)
 {
  if(x!=4)
  {
   fan(x,y);
   m++;
   bfs(x+1,y-3);
   fan(x,y);
   m–;
  }
  if(x==4)
  {
   fan(x,y);
   m++;
   for(i=1;i<=4;i++)
   {
    for(j=1;j<=4;j++)
    {
     if(b[i][j]!=b[1][1])
     { 
      h=1;
      break;
     }
    }
    if(h==1)
    {
     h=0;
     break;
    }
   }
   if(i==5&&j==5)
   {
    if(min>m||min==-1)
    {
     min=m;
    }
   }
   m–;
   fan(x,y); 
  }
 }
 else
 {
  fan(x,y);
  m++;
  bfs(x,y+1);
  fan(x,y);
  m–;
 }
 if(y==4)
 {
  if(x!=4)
  {
   bfs(x+1,y-3);
  }
 }
 else
 {
  bfs(x,y+1);
 }
}
int main()
{
 int n,i,j;
 m=0;
 min=-1;
 for(i=1;i<=4;i++)
 {
  for(j=1;j<=4;j++)
  {
   scanf("%c",&a[i][j]);
   if(a[i][j]=='b')
    b[i][j]=0;
   else
    b[i][j]=1;
  }
  getchar();
 }
 bfs(1,1);
 if(min==-1)
  printf("Impossible\n");
 else
  printf("%d\n",min);
 return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation