本文共 2022 字，大约阅读时间需要 6 分钟。
【题意】
有一个n*m的棋盘，每个小格子有0或1两种状态，现在要把所有的1都变成0，问最少的步数是多少？初始位置在左下角，只有把下面一层的1都变成0后才可以到上一层，只有在每层的最右边和最左边可以向上走(up)，否则只能左右移动(left or right)。只要经过1，就可以把1变成0，只要把最后一个1，就可以立即停止操作。
【Accepted】
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 using namespace std; 17 int n,m; 18 const int maxn=1e2+5; 19 char s[maxn]; 20 int a[16][maxn]; 21 int sum[16]; 22 int ans; 23 int fir[16]; 24 int sec[16]; 25 const int inf=0x3f3f3f3f; 26 int index; 27 void dfs(int cur,int flag,int cnt) 28 { 29 if(cur==index) 30 { 31 if(flag) 32 { 33 int t=cnt+sec[index]-1; 34 ans=min(ans,t); 35 return; 36 } 37 else 38 { 39 int t=cnt+m+2-fir[index]; 40 ans=min(ans,t); 41 return; 42 } 43 } 44 if(flag) 45 { 46 if(sum[cur]) 47 { 48 dfs(cur-1,0,cnt+m+2); 49 dfs(cur-1,1,cnt+2*(sec[cur]-1)+1); 50 } 51 else 52 { 53 dfs(cur-1,1,cnt+1); 54 } 55 } 56 else 57 { 58 if(sum[cur]) 59 { 60 dfs(cur-1,1,cnt+m+2); 61 dfs(cur-1,0,cnt+2*(m+2-fir[cur])+1); 62 } 63 else 64 { 65 dfs(cur-1,0,cnt+1); 66 } 67 } 68 69 } 70 int main() 71 { 72 while(~scanf("%d%d",&n,&m)) 73 { 74 memset(sum,0,sizeof(sum)); 75 memset(fir,-1,sizeof(fir)); 76 memset(sec,0,sizeof(sec)); 77 ans=inf; 78 for(int i=1;i<=n;i++) 79 { 80 scanf("%s",s+1); 81 for(int k=1;k<=m+2;k++) 82 { 83 a[i][k]=s[k]-'0'; 84 sum[i]+=a[i][k]; 85 //每层最右的1的位置 86 if(a[i][k]) 87 { 88 sec[i]=k; 89 } 90 //每层最左的1的位置 91 if(a[i][k]&&fir[i]==-1) 92 { 93 fir[i]=k; 94 } 95 } 96 } 97 int cou=0; 98 //index表示走到第几层为止，因为上面的都是0 99 index=0;100 for(int i=1;i<=n;i++)101 {102 cou+=sum[i];103 if(cou!=0)104 {105 index=i;106 break;107 }108 }109 //特判，如果数据都是0 110 if(index==0)111 {112 printf("0\n");113 continue;114 } 115 //分别表示第几层，当前层的初始位置在最左边还是最右边，步数 116 dfs(n,1,0);117 cout< <
时间复杂度是2^15
没有考虑的都是0的corner case，疯狂wa
转载于:https://www.cnblogs.com/itcsl/p/6931719.html
