当前位置:网站首页>Stepping on a horse (one stroke)

Stepping on a horse (one stroke)

2022-06-13 04:52:00 csuzhucong

Catalog

One , The rules of the game

Two , Simple analysis

1, Nature of the problem

2, The starting point

3、 ... and , Strategic thinking

1, Circle Division

2, Partial solution


One , The rules of the game

The rule of the game is , According to the Japanese character of Ma Zou , Go out of a circle .

  

For those with numbers 2 Of , To go 2 Time , In fact, that is 2 The intersection of cycles .

  

The resulting graph does not quite show the full path , So I added it manually .

Two , Simple analysis

1, Nature of the problem

The problem can be broken down into two problems , First of all , Look for a circle , second , Draw a circle with one stroke .

(1) Find a cycle in an undirected graph , Make the number of times each point passes the same as the given number .

Most of the given numbers are 1, A few are 2

(2) Draw a circle with one stroke , A circle may be self intersecting , It is composed of several circles .

2, The starting point

Because it's a circle , So any point can be the starting point .

But for those with numbers 2 Of , Use numbers 2 It is easier to find the answer by using the point of .

3、 ... and , Strategic thinking

1, Circle Division

  

2, Partial solution

(1) The point with the lowest degree

The point with the lowest degree , Only 2 A neighbor , Such as B My neighbor is AC, be ABC It must be part of the circle .

(2) Path splicing

For simple circles , As long as the two paths have common endpoints , Can be put together into a path . For self intersecting circles , If the public endpoint is not 1, Not necessarily .

Yes 2 And above is the self intersecting circle , Only 1 Is a simple circle .

All in all , If two paths have common endpoints , And this endpoint is not 1, Can be put together to form a path .

   

  such , Look for the rest , It's easier .

In fact, the problem itself has not been greatly simplified , The main thing is that it looks clearer .

 

 

原网站

版权声明
本文为[csuzhucong]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/02/202202280519061620.html