## ACM 马周游解题报告

### 简单的马周游问题

Description

1     2     3       4     5     6

7     8     9       10    11       12

13    14       15    16       17    18

19    20       21    22       23    24

25    26       27    28       29    30

Input

Output

Sample Input

4
-1
Sample Output

（1）原题中文大意

（2）算法思想及解题用到的主要数据结构

（3）详细解题思路

1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.

2. 写一个一般的递归调用自己的函数，表示马在走第几步时到了哪个位置，然后尝试走余下的所有可走位置。

3. 递归函数有两个退出条件。要么下一个要尝试的点已经走过了，要么走到了最后一步，即得解！

（4）逐步求精算法描述

（5）程序注释清单

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <vector>

using namespace std;

const static char row_num = 5;   // 5行

const static char column_num = 6;  // 6列

// 这个全局数组在初始化后会记下每30个有效位置的下一步可走位置.

// elocution[x][0]记个数。最多8个有效可走位置。

char elocution[30][9];

struct coordinate  // 坐标.

{

char _x;  // start from zero.

char _y;

};

// 坐标转序号的函数。

char coordinate2serial_num(coordinate co)

{

char num = co._x * column_num + co._y + 1;

return num;

}

// 序号转坐标的函数。

coordinate serial_num2coordinate(char sn)

{

coordinate co;

co._x = (sn - 1) / column_num;

co._y = sn - co._x * column_num - 1;

return co;

}

// 增量数组.

char increments[8][2] =

{

1, -2, 2, -1, 2, 1, 1, 2,

-1, 2, -2, 1, -2, -1, -1, -2

};

// 得用增量数组来计算每一个位置的下一步有效位置。记到steps里面.

void next_step(char pos, char steps[])

{

char valid_count = 0;

coordinate co = serial_num2coordinate(pos);

coordinate tmp;

char serial_num;

for ( int i = 0; i < 8; i++ )

{

tmp._x = co._x + increments[i][0];

tmp._y = co._y + increments[i][1];

if ( tmp._x < 0 || tmp._x > 4 || tmp._y < 0 || tmp._y > 5 )

{

continue;

}

serial_num = coordinate2serial_num(tmp);

if ( serial_num >= 1 && serial_num <= 30 )

{

valid_count++;

steps[valid_count] = serial_num;

}

else

{

cerr << "Not expected to reach here.\n";

}

}

steps[0] = valid_count;

}

// 初始化记载所有点的下一步可走点的全局表。

void init_elocution()

{

for ( int i = 1; i <= 30; i++ )

{

next_step(i, elocution[i-1]);

}

}

char track[30];   // 记走过的路径.

bool quit_run_horse;

// 上文提高的递归函用函数.

void run_horse(char start_pos, char step_count)

{

if ( quit_run_horse ) // 用来快速退出深嵌套递归调用函数.

{

return;

}

for ( int i = 0; i < step_count; i++ )

{

// 已?经-经-过y这a点?了?.

if ( track[i] == start_pos )

{

return;

}

}

track[step_count] = start_pos; // 记下新走过的位置

if ( step_count == 29 )  // 最后一步则打印出结果。

{

for ( int i = 0; i < sizeof(track); i++ )

{

cout << (int)track[i];

if ( i + 1 != sizeof(track) )

{

cout << " ";

}

}

cout << endl;

quit_run_horse = true;

return;

}

for ( int i = 0; i < elocution[start_pos-1][0]; i++ )

{

run_horse(elocution[start_pos-1][i+1], step_count+1);

}

}

int main(int argc, char* argv[])

{

init_elocution();

int pos;

vector<int> vec;

while(true)

{

cin >> pos;

if (pos==-1)

{

break;

}

vec.push_back(pos);

}

for ( int i = 0; i < vec.size(); i++ )

{

quit_run_horse = false;

run_horse(vec[i], 0);

}

return 0;

}

## knowledge gained from learning git.

# If you inadvertently remove a file of your working copy. Don't worry. Git are good at recovering old versions of files, such as:
$git checkout HEAD — data # show what the file looks like in a certain branch.$git show branch_name:file_name

# In newer versions of Git, git diff –ours is a synonym for git diff HEAD, because it shows the differences between "our" version and the merged version. Similarly, git diff MERGE_HEAD can be written as git diff –theirs. You can use git diff –base to see the combined set of changes since the merge base, which would otherwise be rather awkwardly written as:
git diff $(git merge-base HEAD MERGE_HEAD) # While you are in the process of resolving a conflict, you can use some special git log options to help you figure out exactly where the changes came from and why. Try this:$git log –merge –left-right -p
–merge shows only commits related to files that produced a conflict.
–left-right displays < if the commit was from the "left" side of the merge("our version", the one you started with), or > if the commit was from the "right" side of the merge("their" version, the one you're merging in).
-p shows the commit message and the patch associated with each commit.

If your repository were more complicated and several files had conflicts, you could also provide the exact file names you are interested in as a command line option, like this:
$git log –merge –left-right -p hello # The -s option to git ls-files shows all the files with all stages. If you want to see only conflicted files, use the -u option instead. #$ git checkout -m branch_name
If possible or if specifically requested with the -m option, Git attempts to carry your local change into the new working directory by performing a merge operation between your local modifications and the target branch.

# $git reset –hard ORIG_HEAD If you want to abort or discard the merge after it has finished(that is,after it has introduced a new merge commit), use the above command. Prior to beginning the merge operation, Git saves your original branch HEAD in the ORIG_HEAD ref for just this sort of purpose. You should be very careful here, though. If you did not start the merge with a clean working directory and index, you could geet in trouble and lose any uncommitted changes you have in your directory. # Just show what the file looks like in a branch.$ git show branch_name:file_name

# The command for manipulating remotes is git remote. This operation introduces a few new settings in the .git/config file.

## Diff, Patch, and Friends(diff, patch和他们的相关工具)(第二篇)

Use the diff program to avoid eyestrain and insanity:

diff -u 1 2
— 1 Sat Apr 20 22:11:53 1996
+++ 2 Sat Apr 20 22:12:01 1996
-1,9 +1,9
Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
-modus gradibus desendendi, non nunquam autem
+modus gradibus descendendi, nonnunquam autem
sentit, etiam alterum modum exstare, dummodo
-pulsationibus desinere et de no modo meditari
+pulsationibus desinere et de eo modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

There are several things to notice here:

*

The file names and last dates of modification are shown in a “header” at the top. The dates may not mean anything if you are comparing files that have been passed back and forth by e-mail, but they become very useful in other circumstances.

*

The file names (in this case, 1 and 2—are preceded by — and +++.

*

After the header comes a line that includes numbers. We will discuss that line later.

*

The lines that did not change between files are shown preceded by spaces; those that are different in the different files are shown preceded by a character which shows which file they came from. Lines which exist only in a file whose name is preceded by — in the header are preceded by a – character, and vice-versa for lines preceded by a + character. Another way to remember this is to see that the lines preceded by a – character were removed from the first (—) file, and those preceded by a + character were added to the second (+++) file.

*

Three spelling changes have been made: “desendendi” has been corrected to “descendendi”, “non nunquam” has been corrected to “nonnunquam”, and “no” has been corrected to “eo”.

Perhaps the main thing to notice is that you didn't need this description of how to interpret diff's output in order to find the differences. It is rather easy to compare two adjacent lines and see the differences.

It's not always this easy

Unfortunately, if too many adjacent lines have been changed, interpretation isn't as immediately obvious; but by knowing that each marked line has been changed in some way, you can figure it out. For instance, in this comparison, where the file 3 contains the damaged contents, and file 4 (identical to file 2 in the previous example) contains the correct contents, three lines in a row are changed, and now each line with a difference is not shown directly above the corrected line:

diff -u 3 4
— 3 Sun Apr 21 18:57:08 1996
+++ 4 Sun Apr 21 18:56:45 1996
-1,9 +1,9
Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
-modus gradibus desendendi, non nunquam autem
-sentit, etiam alterum nodum exitare, dummodo
-pulsationibus desinere et de no modo meditari
+modus gradibus descendendi, nonnunquam autem
+sentit, etiam alterum modum exstare, dummodo
+pulsationibus desinere et de eo modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

It takes a little more work to find the added mistakes; “nodum” for “modum” and “exitare” for “exstare”. Imagine if 50 lines in a row had each had a one-character change, though. This begins to resemble the old job of going through the whole file, character-by-character, looking for changes. All we've done is (potentially) shrink the amount of comparison you have to do.

Fortunately, there are several tools for finding these kinds of differences more easily. GNU Emacs has “word diff” functionality. There is also a GNU “wdiff” program which helps you find these kinds of differences without using Emacs.

Let's look first at GNU Emacs. For this example, files 5 and 6 are exactly the same, respectively, as files 3 and 4 before. I bring up emacs under X (which provides me with colored text), and type:

M-x ediff-files RET
5 RET
6 RET

In the new window which pops up, I press the space bar, which tells Emacs to highlight the differences. Look at Figure 1 and see how easy it is to find each changed word.

Figure 1. ediff-files 5 6

GNU wdiff is also very useful, especially if you aren't running X. A pager (such as less) is all that is required—and that is only required for large differences. The exact same set of files (5 and 6), compared with the command wdiff -t 5 6, is shown in Figure 2.
GNU wdiff也很有用，特别是你没有运行X服务的时候。一个分屏工具(比如 less)就足够用来查找大范围的差异了。

Figure 2. wdiff -t 5 6

///////

## Syntax Highlight in DDD DDD的语法高亮

Hello!

Is it possible to enable syntax highlighting in DDD?
I searched through the Google and found this answer:

Sorry, no, this isn’t possible.
The biggest problem is that Motif’s text widget doesn’t
support multiple colours, and would have to be replaced.
That would be an enormous job.

/////////////////////

Is it still impossible (post date is Thu, 10 Feb 2005)?
Are there any workarounds/patches/forks?

## Diff, Patch, and Friends(diff, patch和他们的相关工具)(第一篇)

“Kernel patches” may sound like magic, but the two tools used to create and apply patches are simple and easy to use—if they weren't, some Linux developers would be too lazy to use them…
"内核补丁"听起来相当之神奇，但是有两个用来创建补丁和应用补丁的工具却简单易用。如果它们很难用的话，一些Linux开发者才懒得用它们呢。

Diff is designed to show you the differences between files, line by line. It is fundamentally simple to use, but takes a little practice. Don't let the length of this article scare you; you can get some use out of diff by reading only the first page or two. The rest of the article is for those who aren't satisfied with very basic uses.
diff这个工具设计成可以向你展示文件之间行与行的区别。它使用起来是相当的简单，但需要一点练习才习。你千万不要让长长的介绍文档把你吓住。你可以先只读前一两页文档，这样你就可以使用diff来开展一些工作了。余下的diff介绍文档是写给那些对基本用法非常不满的奇异人士的。 http://blog.ykyi.net

While diff is often used by developers to show differences between different versions of a file of source code, it is useful for far more than source code. For example, diff comes in handy when editing a document which is passed back and forth between multiple people, perhaps via e-mail. At Linux Journal, we have experience with this. Often both the editor and an author are working on an article at the same time, and we need to make sure that each (correct) change made by each person makes its way into the final version of the article being edited. The changes can be found by looking at the differences between two files.
diff被开发者用来同一个源文件的比较不同版本之间的区别。这还可以有很多其它的用途。比如，当编辑一个在很多人之间通过email传递的文档时，diff工具非常方便。在Linux Journal网站，我们经历过这些。编辑和作者同时修改同一个文章的情况非常常 见，我们需要确保每个人所作的修改都被正确应用到这篇文章的正确位置。被修改的部分可以通过比较两个文件的区别得到。

However, it is hard to show off how helpful diff can be in finding these kinds of differences. To demonstrate with files large enough to really show off diff's capabilities would require that we devote the entire magazine to this one article. Instead, because few of our readers are likely to be fluent in Latin, at least compared to those fluent in English, we will give a Latin example from Winnie Ille Pu, a translation by Alexander Leonard of A. A. Milne's Winnie The Pooh (ISBN 0-525-48335-7). This will make it harder for the average reader to see differences at a glance and show how useful these tools can be in finding changes in much larger documents.

Quickly now, find the differences between these two passages:

Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
modus gradibus desendendi, non nunquam autem
sentit, etiam alterum modum exstare, dummodo
pulsationibus desinere et de no modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
modus gradibus descendendi, nonnunquam autem
sentit, etiam alterum modum exstare, dummodo
pulsationibus desinere et de eo modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

You may be able to find one or two changes after some careful comparison, but are you sure you have found every change? Probably not: tedious, character-by-character comparison of two files should be the computer's job, not yours.

## fsockopen真好用,PHP的高级别网络函数！

fsockopen()
returns a file pointer which may be used together with the other file functions (such as fgets(), fgetss(), fwrite(), fclose(), and feof())
fsocketopen返回一个文件指针，然后就可以用常用的文件函数操作它啦！！！和操作文本一件一样~~~ 比 Java 的 java.io.socket 类还要方便~~虽然java也抽象的不错，但我就是嫌流对象封装太厚了。人生苦短，何必自找麻烦呢。

$fp = fsockopen(“udp://127.0.0.1”, 13,$errno, $errstr); if (!$fp) {
echo “ERROR: $errno –$errstr
\n”;
} else {
fwrite($fp, “\n”); echo fread($fp, 26);
fclose(\$fp);
}
?>