想了4个多小时 各种超时啊， 求思路啊，求思路， 有AC的代码最好了， 可以用来研究，

 第一个贴AC代码的100分归他， 附上思路另加分啊
http://acm.zju.


我的思路是这样的 用DFS来搜
void DFS(int x, int y, int str[], int step, int val[10][5],int tmpp)

x,y 表示点坐标
step用来存步数
str用来存路径  （既存当前点的上一个点，像链表形式方式那样来存）
val[][0] val[][1] val[][2] 用来存每行0，1，2的个数
val[][4]用来存当前行已经访问过的那类数（这是用来剪支用的  如果当前行访问过了1就不能访问2的点了  反之也一样）
tmpp 是用来压缩存每行时候都已经是0和1 或0和2了  是就在相应的行号位上标记为1

然后加了两个普通的剪支方法：
 if(step + abs(x2-x) +abs(y2-y) >= tmpnum) return;
 if(step >= tmpnum) return; 其中tmpnum是存上次收到结果时的最小步数，x2,y2是目标坐标


然后就各种超时啊  是不是我思路原本就错了  还是没有想到犀利的剪支方法啊， 求解啊

用栈就可以，每次分别向四个方向测试，能走就进栈。
然后修改走过的地方的值，表示走过。
如果遇到死胡同，就出栈，直到走出去，或者空栈表示无解。

枚举题 复杂度O(n*m*2^n)

[ 本帖最后由 卧龙孔明 于 2012-4-9 23:02 编辑 ]

枚举每一横行最终变成白色还是黑色，然后验证一下变色的方格是否组成了一条不自交的线就可以了

太晚了。明天试一下。希望能赶在小曹前面

就是先构图， 再一次DFS是吧

"验证一下变色的方格是否组成了一条不自交的线"
这有什么算法不啊 我图构好用DFS回溯来判断还是TL

dfs一遍就行了，每个点至多访问一次，所以每次dfs复杂度是O(nm)，乘上枚举复杂度O(2^n)，就得到O(nm2^n)

DFS一次不行的吧， 他是要一条线啊
不回溯到达终点是不一定包含所有的点啊， 不是么？？

还有我一开始题目读错了  以为要输出满足条件的最短的那条- -！
不过读对了还是超时， 孔明先生，要不给个AC代码让我研究研究啊

囧，想错了，求的不是欧拉路而是哈密顿路……
这样如果搜不过的话用连通性状态压缩dp吧