小弟我被小学生难住了(试试）

我被小学生难住了(各位大哥试试）
一天，表妹问我：
00000
00000
00000
  0000
00000  
怎样用一条线连起来？不能斜画   就是说比如：   左上0.0   不能连到1.1   另外0.0   不能直接连到   2.0   就是说只有上下左右能连   而且每个0只能连一次。
我想了想   咱好歹是个学计算机的。这类类似穷举的问题就交给计算机来做。没想到真正实现的时候却不知从何下手！
汗颜啊。如果采用深度搜索，怎样才能给走过的路径置一个位   以免死循环呢？另外要采用什么数据结构才好？堆栈貌似不太合适   队列也不成。咋办？

------解决方案--------------------
大伙儿都被自己的计算机思维给害了。。
这道题又没有让给出全解，一个解就可以了。。。

就走一条蛇行线好了。。

-----
----|
|--||
||-||
|---|
------解决方案--------------------
给个无解的证明吧，结帖吧。

对此题，可以这样看。
容易看出，如果有解，左上角的圈肯定是起点或终点。我们去掉这个位置，无妨设它下面的位置是起点。
现在把所有的位置交替涂色：
○×○●○
●○●○●
○●○●○
●○●○●
○●○●○
可以看出，除去左上角后，黑的位置比白的位置少一个。但现在是从黑位置开始走，连成的线肯定是“黑白黑白……黑”或“黑白黑白……白”，要么黑白一样多，要么黑的比白的多一个，导致矛盾。所以无解。
------解决方案--------------------
编了个程序，结果证明是无解的。

#include <iostream>
using std::cout;
using std::endl;

const size_t GRAPH_SIZE = 5;
const size_t POSITIVE_OFFSET = 1;

bool StepZeroGraph(size_t zero_graph[][GRAPH_SIZE], size_t row, size_t col,
size_t& step_num)
{

if ( --step_num == 0)
{
return true;
}

static size_t try_step[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

for (size_t i = 0; i < sizeof(try_step) / sizeof(try_step[0]); i++)
{
size_t next_row = row + try_step[i][0];
size_t next_col = col + try_step[i][1];
if ( next_row > = 0
&& next_row < GRAPH_SIZE
&& next_col > = 0
&& next_col < GRAPH_SIZE)
{
if (zero_graph[next_row][next_col] != 0)
continue;

zero_graph[row][col] = next_row*GRAPH_SIZE + next_col + POSITIVE_OFFSET;
if (StepZeroGraph(zero_graph, next_row, next_col, step_num))
return true;
}
}

zero_graph[row][col] = 0;
step_num++;
return false;
}

inline void PrintResult(size_t row, size_t col, size_t& step_num)
{
cout < < step_num++ < < ":\t "
< < "row = " < < row < < "\t "
< < "col = " < < col < < endl;
}

int main()
{
size_t zero_graph[GRAPH_SIZE][GRAPH_SIZE] = {0};
size_t step_num = GRAPH_SIZE*GRAPH_SIZE;

size_t row = 4;
size_t col = 0;
zero_graph[3][0] = row * GRAPH_SIZE + col + POSITIVE_OFFSET;
// zero_map[3][0]这里不能通过，所以设一个非0值
// 从题义知，zero_map[4][0]必然是开始或结束点
// 不失一般性，将zero_map[4][0]设为开始点
step_num--;


if (StepZeroGraph(zero_graph, row, col, step_num))
{
while (zero_graph[row][col] != 0)
{
PrintResult(row, col, step_num);
size_t next = zero_graph[row][col] - POSITIVE_OFFSET;
row = next / GRAPH_SIZE;
col = next - row * GRAPH_SIZE;
}
PrintResult(row, col, step_num);
}
else
{
cout < < "Solution NOT FOUND !! " < < endl;
}

system( "pause ");
}

输出是 Solution NOT FOUND !!
在调试时插入计数器发现，一共递归了43207次。

看了一下LS的证明，我觉得完全正确。


------解决方案--------------------
milksea(航航 | 啥都不会咋办)的思路是对的，不过证明过程有误，不一定是要黑的作为起点，统计黑白位置的数量也有误。
由图可以看出不论怎么走，根据黑白相间的路线统计出都应该是黑的位置相等或相差一个，而这个图白的位置多出两个，明显是不可能形成黑白相间的路线的，因此无解。