问题描述
这里有若干个字母组成的列。从最顶层开始，取走相同的字母，之后下一行的字母顶上，比如两个I（在B和C列），之后下面的两个P顶上，在之后可以取走四个P，以此类推。取字母只能取顶层连续向下。问：如何得到最少的步骤把字母全部取光？
解决方案
解决方案二：
这个，好像只能回溯吧？分少没动力。找现成的代码吧。
解决方案三：
我在VBGood论坛得到了beyondyf的解答。我用了一下的类来解决上面的问题，但算5X8的矩阵要好一个小时以上。高人们我如何设置搜索的深度来缩短计算时间。原贴地址是http://www.vbgood.com/viewthread.php?tid=66872&extra=page%3D1&page=5
classRubbish{publicRubbish(int[,]map){this.map=map;//map是从字符数组见上图，转到int的数组row=map.GetLength(0);col=map.GetLength(1);point=newint[col];remove_step=newint[map.Length];remove_step_count=0;remove_step_save=newint[map.Length];remove_step_save_count=0;Done();}publicint[]Result(){int[]ret;ret=newint[remove_step_save_count];for(inti=0;i<remove_step_save_count;i++)ret[i]=remove_step_save[i];returnret;}privatevoidDone(){int[]a;a=GetCanBeRemovedElement();int[]p;p=newint[point.Length];for(inti=0;i<p.Length;i++)p[i]=point[i];if(a.Length==0){if(remove_step_save_count==0||remove_step_save_count>remove_step_count){for(inti=0;i<remove_step_count;i++)remove_step_save[i]=remove_step[i];remove_step_save_count=remove_step_count;}return;}for(inti=0;i<a.Length;i++){remove_step[remove_step_count]=a[i];remove_step_count++;Remove(a[i]);Done();for(intj=0;j<point.Length;j++)point[j]=p[j];remove_step_count--;}}privatevoidRemove(inte){for(inti=0;i<col;i++)if(point[i]<row)if(map[point[i],i]==e)point[i]++;}privateint[]GetCanBeRemovedElement(){System.Collections.ArrayLista=newSystem.Collections.ArrayList();for(inti=0;i<col;i++){if(point[i]<row&&a.IndexOf(map[point[i],i])<0)a.Add(map[point[i],i]);}int[]ret;ret=newint[a.Count];for(inti=0;i<a.Count;i++)ret[i]=(int)a[i];returnret;}privateint[,]map;privateint[]point;privateint[]remove_step;privateint[]remove_step_save;privateintremove_step_count;privateintremove_step_save_count;privateintrow;privateintcol;}
解决方案四：
这里是另一高人的程序没代码。但他就是利用递归的深度优先搜索遍历解空间。我如何改上面的代码来减少计算时间。
解决方案五：
感觉很像某个游戏啊，mark，待会有空试试
解决方案六：
第一次取完两个I之后两个P顶上，那最后一行的BC列会变成什么？
解决方案七：
privateList<string>listCol=newList<string>();privateList<List<string>>listMatrix=newList<List<string>>();privatestaticList<int>sol;privateList<int>temp;privateintiColCount;privatevoidForm1_Load(objectsender,EventArgse){string[][]strAy={newstring[]{"A","C","S","Q","T","I","P","R"},newstring[]{"I","P","A","S","D","W","W","R"},newstring[]{"I","P","A","S","S","E","W","E"},newstring[]{"P","S","A","H","J","K","H","G"},newstring[]{"P","G","R","E","W","D","F","G"},newstring[]{"L","K","H","G","T","Y","R","D"},newstring[]{"S","D","F","G","H","J","Y","G"},newstring[]{"A","D","F","F","D","G","H","A"}};iColCount=strAy.Length;for(inti=0;i<strAy.Length;i++){listMatrix.Add(newList<string>());for(intj=0;j<strAy[i].Length;j++)listMatrix[i].Add(strAy[i][j]);}}privatevoidbutton1_Click(objectsender,EventArgse){temp=newList<int>();sol=newList<int>();getSol(listMatrix);Console.WriteLine("BestSol:");for(inti=0;i<temp.Count;i++)Console.Write(sol[i].ToString());Console.WriteLine();}privatevoidgetSol(List<List<string>>listMatrix){inti;for(i=0;i<listMatrix.Count;i++){if(listMatrix[i].Count>0)break;}if(i==listMatrix.Count){for(intj=0;j<sol.Count;j++)Console.Write(sol[j].ToString());Console.WriteLine();if(sol.Count<temp.Count||temp.Count==0)temp=sol;return;}List<string>listHave=newList<string>();for(i=0;i<iColCount;i++){while(listMatrix[i].Count==0&&i<iColCount-1)i++;if(listMatrix[i].Count>0&&!listHave.Contains(listMatrix[i][0])){stringstrNow=listMatrix[i][0];listHave.Add(strNow);sol.Add(i);List<int>tempremove=newList<int>();for(intj=i;j<iColCount;j++){while(listMatrix[j].Count==0&&j<iColCount-1)j++;if(listMatrix[j].Count>0&&listMatrix[j][0]==strNow){listMatrix[j].RemoveAt(0);tempremove.Add(j);}}getSol(listMatrix);for(intj=0;j<tempremove.Count;j++){listMatrix[tempremove[j]].Insert(0,strNow);}sol.RemoveAt(sol.Count-1);}}}
试着写的，发现代码跟2楼很相似。看来想到的都是回溯。执行起来估计一年不够吧。如果优化的话，最多也就是把2楼代码的for(inti=0;i<p.Length;i++)[我的for(i=0;i<iColCount;i++)]这句改一下，改成优先循环能去掉较多的字母的方案。好处是可以尽快得到比较优秀的解,想得到最优还是要完全遍历才可以。
解决方案八：
是不是该某列为空删除或两侧列相邻的规则啊不然如何取光
解决方案九：
简化问题就是：某字符矩阵，从上往下取走字母（不能取中间层），一次只能取走的列最顶端相同字母。依次取走，并把取走的字母按循序组成一个字符串返回输出。
解决方案十：
引用6楼HimeTale的回复:
如果优化的话，最多也就是把2楼代码的for(inti=0;i<p.Length;i++)[我的for(i=0;i<iColCount;i++)]这句改一下，改成优先循环能去掉较多的字母的方案。
请赐教，如何优化这段代码。不然实在是太慢了。8X4000的矩阵估计到人类灭绝也得不到结果。
解决方案十一：
下沉太快了