Math,OI,ACM,Game,Music,All My Love

       用自己写的小引擎,自娱自乐写的一个小游戏呵呵^_^,感觉还不错贴张图上来呵呵

无事上了下SGU,顺便刷了几题,其实称不上刷呵呵
把简析打上来吧!
SGU106:欧里几德扩展算法解二元不定方程
SGU107:根据模3的特殊性
SGU108:算法简单枚举,实现起来要用一个1gn*9的循环数组来实现
SGU109:构造法,构造方法比较多,主要有两种比较容易实现:1,消最外层的黑,然后消最外层的白.2,一直消斜对角线
SGU112:高精度
SGU113:分解质因数
SGU114:初中绝对值方程问题:|x-a1|+|x-a2|+...+|x-an|的最小值
SGU115:难度仅高于a+b
SGU116:可重复背包问题,先求出所有超级素数这些就相当于物品,然后N为背包再DP
SGU117:将除数分解因式,判断因子在被除数中是否有
SGU118:函数f的性质 f(a+b)=f(f(a)+f(b)),数学归纳法可证推出f(a*b)=f(f(a)*f(b))然后用这两个公式去求
SGU119:d=gcd(a,b,c),a/d,b/d,c/d,然后有(a*i % n,b*i % n)为解

分支限界，在可能与不可能之间

或许，我太无知；或许，我太猖狂，但我知道我该做什么，我能做什么。

因为，我学过：分支限界。分支，让我知道什么事不能做。这样我不会把精力放在不必要的地方，适当的约束自己，给自己一些有限的自由。因为分支，我不会肆无忌弹，也不会太过虚浮，我会把自己圈在一个适当的范围里，做自己该做的事情。这就是分支教会我的。

限界，让我判断自己的能力，于是为自己寻找更为踏实的路。我相信每个人都有不同的能力，也拥有自己的长与短。扬长避短，将最擅长的一面展示出来，他能够创造的价值才是最大的。当然这其中自然要给自己"限界"，没有人是万能的，在自己能力所及的范围能做出成绩来，这样的人生就是成功的。客观的衡量自己，并为自己限界。把界限之内的事情做到最好，这就是我要的人生。能做的事情做好它，做不到的事情放弃它！这就是分支限界教给我的。

每个人，都应该作出客观的分支限界。知道自己该做什么、能做什么，给自己的生活圈定一个大致的方向，今后的路才能走的更加清楚。看到很多人，在不属于自己的岗位上，努力而痛苦的活着。我想，如果他们做过分支限界会多好！现在，他们那么努力只能做到和别人一样（甚至有些还不如别人），但如果在另一方面，他们会是多么出色阿！也见过，有的人非要做自己做不了的事情。身败名裂，最后化作了外人的笑谈。全然是不懂分支限界的后果。 如果你和我一样，还有机会，慎重的为自己分支限界吧！在生活与事业中找到属于自己的天下！

人生的算法
        如果生活是一个难解的数学问题。
        那么，每个人都在寻找一个适合自己的算法。
        有人天生喜欢遍历，希望能够踏遍千上万水，希望扮演各种人生角色，希望丰富与多彩。
        有人一生注定贪婪，眼界不宽，却也活的快活，或称之为"务实"，或称之为"狭隘"，但终究是一种活法。
        有人注定适用"穷搜"，辛辛苦苦勤勤恳恳一辈子，付出太多，获得的并不多。
        有人却善用"时空权衡"，用最少的时间办最多的事，的确"精明"。
        有人会"分治"，太多难题倒也迎刃而解，于是生活倒也轻松而精彩。
        有人常"回溯"，错的太多，后悔太多。
        有人压根没有算法，于是盲目的生活、盲目的做事，最后一无所获。
        有人却能"动态规划"，有了目标，于是生活便有了很多意义。
        这些就是生活，这些也是算法。

忽然发现，算法未必要依赖于计算机。
每个人的大脑，都可以容纳很多程序，度过人生、经营人生或是享受人生。
这些算法的复杂度是无从计算的，因为生活还要继续，一切尚未完结。最好怎样、最坏怎样谁都无从知道。
这些算法没有什么标准，各色的人生，多彩的生活，需要面对的问题也不一样。于是，需要用不同的算法去面对多样的生活。
所以，不要轻易的说："你这么做不对"因为，不到最后，你无法判断生活的对错。一切还是交由时间来裁判吧！
所以，不要在乎别人说："你看某某某怎样......"珍视自己的生活，做好自己才是最重要的。
 
关于人生的算法，该是一种选择，是对于生活、对于未来的选择。
关于人生的算术，该是一种计划，是对于今天，对于明天的计划。
纵然，"计划赶不上变化"，但我不愿，毫无计划的生活！
于是，我开始为自己设计属于自己的算法。

         好久没打代码了，有点不习惯了，呵呵
以后就会多花时间打代码的了，数学的学习暂告一个段落!

三次方程新解法——盛金公式解题法

　　呵呵，一直搞数学懒得来，总算是有收获呵呵，还算没白花时间，程序也搁下了，现在越来越懒打代码了，不知道这样下来，自己还能不能做个合格的程序员了^_^，反正大部分工作也差不多是数学，如果不学，老大给个任务不会那就不好了，本来平时没事，如果给个事又不会做那只有死@_@，不管怎么样，老大分下来的数学任务还是得秒杀的^_^，可是秒杀谈何容易，需要强大的功底啊!!这个月过完估计就要结束数学的学习了，科学领域太广了，不管哪门都不可能短时间内学到非常牛。哎~~~~~~突然发现这世界上天才真多。看来自己得专一了，一向总是挺贪的，却不能静下心来学习哪一门。得改改这个不好的本性(可惜人人都知道本性难移)，哎~~~~~最近生活MS过于平静了，得干点什么找找对生活的激情了，出来学校才知道在学校真的很爽呵呵。
        最近工作时没什么事，平时边看数学看电视呵呵，一心二用，不过好像这样也可以的。音乐啊音乐，好久没有好的音乐了，杰伦似乎不再像以前那么有创作能力了，音乐似乎也商业化了，哎~~~~ 终居还是逃不出这么一句话“大众化=庸俗”，世界永远只有少数人是高贵的，否则就没高贵的概念了，世界就是这样相对的。虽然自己也和高贵沾不上边，但是至少也不会和那么庸俗无聊的人同流全污吧。期待某音乐天才的出现，这世界上的天才很多的，为什么音乐天才这么少？
       似乎我也不知道说到哪去了，哎~~~~~，语文不好真是不爽啊，不写了明显在扯淡。

        四大名蓍中偶西游记读了二遍，水浒读了三遍，三国和红楼梦都没读，三国有必有去读一下了，俗话说老不读三国，少不读水浒，偶偏偏相反。说起来，偶还是最喜欢水浒，喜欢那种大口吃肉，大口喝酒，偶向来不喜欢政治。西游记么也还可以的，三国政治性太强，看一点就没看下去的欲望了，红楼梦这种SB作品妈的真不知道怎么被评入四大名著了的，完全是狗屁嘛。反正偶是看不下去的。看红楼你不如要我来看佛经，还不如数学书好看。有机会看下三国，不是看，最好是有某人给偶讲一遍~~~~~显然是不可能的，现在好像没有说书的了，要是有偶去听说书的多好，呵呵~~~~~现在越来越懒了，懒得自己去看。啊~~~找个老先生开个说书+茶管生意应该很不错的说。

STL : Standard Template Library 标准模版库
//有人说：这是给C++中最激动人心的东西，取了一个最无聊的名字。

重要的概念：

容器(container):

内部实现: 数组 // 就是没有固定大小的数组，vector直接翻译是向量的意思
vector
// T 就是数据类型，Alloc是关于内存的一个什么东西，RoBa没有仔细讲，一般是使用默认参数。
支持操作:
begin(), //取首个元素，返回一个iterator
end(), //取末尾（最后一个元素的下一个存储空间的地址）
size(), //就是数组大小的意思
clear(), //清空
empty(), //判断vector是否为空
[ ]  //很神奇的东东，可以和数组一样操作
//举例： vector a;   //定义了一个vector
//然后我们就可以用a[i]来直接访问a中的第i + 1个元素！和数组的下标一模一样！
push_back(), pop_back() //从末尾插入或弹出
insert() O(N)  //插入元素，O(n)的复杂度
erase() O(N)  //删除某个元素，O(n)的复杂度
可以用于数组大小不定且空间紧张的情况

Sample: TOJ1743 King’s Treasure  //这题如果直接开数组的话，需要开到一个240,000 * 240,000的二维数组
代码：
#include
#include
using namespace std;

vector a[240010]; //一个vector组成的数组！

int main()
{
 int cases,n,i,t,head,tail,src,pans;
 scanf("%d",&cases);
 while (cases--) {
  scanf("%d",&n);
  for (i = 1 ; i <= n ; i++) a[i].clear();
  for (i = 2 ; i <= n ; i++) {
   scanf("%d",&t);
   a[i].push_back(t);
   a[t].push_back(i);
  }
............

Iterator用法举例:
#include
#include
using namespace std;
int main()
{
 int n,i;
 vector vi; //类似于我们定义一个数组，同 int vi[1000]; 但vector的大小是自动调整的
 vector ::iterator itr;  //两个冒号，很怪的定义方式，但就是这么定义的
 while (scanf("%d",&n) != EOF)
  vi.push_back(n);
 for (i = 0 ; i < vi.size() ; i++)
  printf("%d\n",vi[i]);
 for (itr = vi.begin() ; itr != vi.end() ; itr++) //也支持++操作
  printf("%d\n",*itr);
 return 0; 
}

类似   //双端队列，两头都支持进出
支持push_front()和pop_front() 
是的精简版:)  //栈，只支持从末尾进出
支持push(), pop(), top()
是的精简版   //单端队列，就是我们平时所说的队列，一头进，另一头出
支持push(), pop(), front(), back()

内部实现: 双向链表  //作用和vector差不多，但内部是用链表实现
list
支持操作:
begin(), end(), size(), clear(), empty()
push_back(), pop_back()  //从末尾插入或删除元素
push_front(), pop_front()
insert() O(1)  //链表实现，所以插入和删除的复杂度的O(1)
erase() O(1)
sort() O(nlogn),不同于中的sort
//不支持[ ]操作！

内部实现: 红黑树 //Red-Black Tree，一种平衡的二叉排序树
set //又是一个Compare函数，类似于qsort函数里的那个Compare函数，作为红黑树在内部实现的比较方式
insert() O(logn)
erase() O(logn)
find() O(logn) 找不到返回a.end()
lower_bound() O(logn) 查找第一个不小于k的元素
upper_bound() O(logn) 查找第一个大于k的元素
equal_range() O(logn) 返回pair

允许重复元素的

的用法及Compare函数示例:
struct SS {int x,y;};
struct ltstr {
 bool operator() (SS a, SS b)
 {return a.x < b.x;}  //注意，按C语言习惯，double型要写成这样：return a.x < b.x ? 1 : 0;
};
int main()
{
 set st;
 …
}

允许重复元素, 没有[]运算符

Sample : TOJ 1378 Babelfish

Code: (0.4k)  //只有0.4K的代码....
#include
#include
#include

map mp;

int main()
{
 char buf[100],s1[100],s2[100];
 while (gets(buf)) {
  if (strlen(buf) == 0) break;
  sscanf(buf,"%s%s",s1,s2);
  mp[(string)s2] = (string)s1; //这里的string s2，起到了类似于数组下标的作用！！
 } 
 while (gets(buf)) {
  if (mp.find((string)buf) != mp.end())
   printf("%s\n",mp[(string)buf].c_str());  //mp[(string)buf]返回值是string类型，要转化成C语言能识别的字符串数组，加上.c_str()即可
  else printf("eh\n");
 }
return 0;
}

内部实现: 堆   //优先队列，听RoBa讲得，似乎知道原理了，但不明白干什么用的
priority_queue
支持操作:
push() O(n)
pop() O(n)
top() O(1)
See also: push_heap(), pop_heap() … in

用法举例:
#include
#include
using namespace std;

priority_queue maxheap; //int最大堆

struct ltstr {   //又是这么个Compare函数，重载运算符？？？不明白为什么要这么写...反正这个Compare函数对我来说是相当之神奇。RoBa说了，照着这么写就是了。
 bool operator()(int a,int b)
 {return a > b;}
};
priority_queue ,ltstr> minheap; //int最小堆

内部实现: Hash表, of course //内部用哈希表实现的map，据说还不是现在的C++标准，但因为太好用了，所以估计早晚要成为标准的~
hash_map
重载HashFcn和EqualKey
支持操作:
insert(); O(1)
earse(); O(1)
[ ];   O(1)
示例：Again TOJ 1378 Babelfish
See also:

#include
#include  //??   //因为不是C++标准，所以要加.h
#include
using namespace std;

struct calc_hash {
 size_t operator()(string str) const {
  unsigned long h = 0;
  int i;
  for (i = 0 ; i < str.size() ; i++) {
   h <<= 5;　　　　　　　　　　　//这个就是哈希函数，从字符串到int的印射函数，可以去网上找
   h |= str[i] - 'a';
  }
  return (size_t)h; //h%M??      //h是否需要一个上限？据说系统会自动处理，不必人工添加
 }
};

struct eqstr {
   bool operator()(string s1, string s2)
 {return s1 == s2;}
}; //本题此处可省略          //可以省略？？ 因为string作为一个常用类型，系统中有默认的比较函数，不必自己写
int main() {
 hash_map hp;
 char buf[100],s1[20],s2[20];
 while (gets(buf)) {
  if (strlen(buf) == 0) break;
  sscanf(buf,"%s%s",s1,s2);
  hp[s2] = s1; 
 } 
 while (gets(buf)) {
  if (hp.find((string)buf) != hp.end())
   printf("%s\n",hp[(string)buf].c_str());
  else printf("eh\n");
 }
 return 0; 
}

   //更神奇的东西！
1.sort()
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
区间[first,last)
Quicksort,复杂度O(nlogn)
(n=last-first,平均情况和最坏情况)

用法举例:
1.从小到大排序(int, double, char, string, etc)
const int N = 5;
int main()
{
 int a[N] = {4,3,2,6,1};
 string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”};
 sort(a,a+N);
 sort(str,str+N);
 return 0;
}
2.从大到小排序（需要自己写comp函数)
const int N = 5;
int cmp(int a,int b) {return a > b;}
int main()
{
 int a[N] = {4,3,2,6,1};
 sort(a,a+N,cmp);
 return 0;
}
3. 对结构体排序
struct SS {int first,second;};
int cmp(SS a,SS b) {
 if (a.first != b.first) return a.first < b.first;
 return a.second < b.second;
}

v.s. qsort() in C (平均情况O(nlogn)，最坏情况O(n^2))    //qsort中的cmp函数写起来就麻烦多了！
int cmp(const void *a,const void *b) {
 if (((SS*)a)->first != ((SS*)b)->first)
  return ((SS*)a)->first – ((SS*)b)->first;
 return ((SS*)a)->second – ((SS*)b)->second;
}
qsort(array,n,sizeof(array[0]),cmp);

sort()系列:
stable_sort(first,last,cmp); //稳定排序
partial_sort(first,middle,last,cmp);//部分排序
将前(middle-first)个元素放在[first,middle)中，其余元素位置不定
e.g.
int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
partial_sort(A, A + 5, A + 12);
// 结果是 "1 2 3 4 5 11 12 10 9 8 7 6".
Detail: Heapsort ,
O((last-first)*log(middle-first))

sort()系列:
partial_sort_copy(first, last, result_first, result_last, cmp);
//输入到另一个容器，不破坏原有序列
bool is_sorted(first, last, cmp);
//判断是否已经有序
nth_element(first, nth, last, cmp);
//使[first,nth)的元素不大于[nth,last), O(N)
e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5
nth_element(A,A+6,A+12);
Output: 5 2 6 1 4 3 7 8 9 10 11 12

2. binary_search()
bool binary_search(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
在[first,last)中查找value，如果找到返回Ture,否则返回False
二分检索，复杂度O(log(last-first))
v.s. bsearch() in C

Binary_search()系列
itr upper_bound(first, last, value, cmp);
//itr指向大于value的第一个值(或容器末尾)
itr lower_bound(first, last, value, cmp);
//itr指向不小于valude的第一个值(或容器末尾)
pair equal_range(first, last, value, cmp);
//找出等于value的值的范围 O(2*log(last – first))
int A[N] = {1,2,3,3,3,5,8}
*upper_bound(A,A+N,3) == 5
*lower_bound(A,A+N,3) == 3

make_heap(first,last,cmp) O(n)
push_heap(first,last,cmp)  O(logn)
pop_heap(first,last,cmp)  O(logn)
is_heap(first,last,cmp)  O(n)
e.g:
vector vi;
while (scanf(“%d”,&n) != EOF) {
 vi.push_back(n);
 push_heap(vi.begin(),vi.end());
}

Others interesting:
next_permutation(first, last, cmp)
prev_permutation(first, last, cmp)
//both O(N)
min(a,b);
max(a,b);
min_element(first, last, cmp);
max_element(first, last, cmp);

Others interesting:
fill(first, last, value)
reverse(first, last)
rotate(first,middle,last);
itr unique(first, last);
//返回指针指向合并后的末尾处
random_shuffle(first, last, rand)

Some Others:
More container: Rope, Slist, Bitset …
More about iterator
Memory allocation
Function object

 说真话以前蛮怕A*的，A*算法的两个表一个用最大(最小)堆保存待扩展结点，一个要用二叉排序树或者哈希来表示已扩展结点，是个人都知道这两个数据结构写起来会死人，加上本人特懒更不可能了。
        以前总是觉得宽搜多好，简单好写，只是开销内存大点，没想到和A*算法比起来真是差得远啊~~~~~那个效率啊~~~不敢想像。
        还是简单介绍一下A*算法
首先A*算法属于启发式搜索，启发式搜索和盲目搜索的不同之处在于，他们扩展结点的方式不同，他的扩展方式其实和Dijkstra算法的思想一样，启发式搜索必需有一个对结点进行评估的函数f(n)=g(n)+h(n)，许多书上么说的很抽象，我开始看A*也是怎么也看不懂，只是后来用Dijkstra算法时偶然明白的。所以偶就拿走路来比方。我们从起点到终点，有很多路，就是一个图。f(n)表示一个结点从起点到终点的路程，他的值从两个方面得到，g(n)表示结点已经走过的路，h(n)表示我们现在在这个地方到终于还有多远(但是这个值是不确定的，也许有些路看起来很近其实很远，有些路么看起来很远其实很近。
       在dijkstra算法里我们每次将当前距离最小的路径扩展di=di-1+dist[i,i-1]
如果最短路dijkstra算法也不懂，那我也没办法了~~~~~~您就继续看书吧
在图中我们根本不知道如何猜测一个结点到终点有多远，可能是0也可能是无限大，所以如果我们估错了，也许我们就找不到解了，所以只有不估那么h(n)=0.于是f(n)=g(n) A*算法此时就是dijkstra算法了~~~~~~~~。
不知道您看了这些有没有一点点启发文采太差了偶。

但是在8OR15数码里面我们就可以估计至少还要多少步才能到目标。
比如：
1 2 3           1 2 3
4 5 6------->4 0 6
7 8 0            7 5 8
你看相当于只有0是能动的，每次最多只能使一个子像目标移动一格(最好的情况)，比如这里5至少要移动一步，8至少也要移动一步，所以至少要2点，此时h(n)=2
这里有两个程序，一个是用pascal写的宽搜8数码，一个是C++写的A*的8数码
对于周一个数据：
0 1 2
3 4 5
6 7 8 

1 2 3
4 5 6
7 8 0
普通的BFS根本搜不出来，而A*可以瞬间出解~~~~~

#include <fstream>
#include <queue>
using namespace std;
ifstream inf("Asart.txt");
ofstream ouf("Asart.out");

//priority_queue<int, vector<int>, less<int> > intq;  //最大堆
//priority_queue<int, vector<int>, greater<int> > intq;  //最小堆

struct Heap_Node
{
 int a[3][3];
 Heap_Node* father;
 int g, h;
 int x, y;
 bool operator < (const Heap_Node &t) const
    {return g + h > t.g + t.h  ;}  //如果为"<"最大堆，如果为">"最小堆
};
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int Fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
Heap_Node Target, Strat;
int TargetArr[9][2];
priority_queue<Heap_Node>TableOne;
bool TableTwo[362879];

int Change(Heap_Node State)
{
 for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
  {
   TargetArr[State.a[i][j]][0]=i;
   TargetArr[State.a[i][j]][1]=j;
  }
}

int Value(Heap_Node State)
{
 int s = 0;
 for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
     if (State.a[i][j] != 0)
      s+=abs(TargetArr[State.a[i][j]][0]-i)+abs(TargetArr[State.a[i][j]][1]-j);
  return s;
}
 

int Hash(Heap_Node State)
{
 int i, j, s=0;
 int a[9],t[9];
 for (i = 0; i < 3; i++)
    for(j = 0; j < 3; j++) a[i*3+j] = State.a[i][j];
 for (i = 8; i >= 0; i--)
 {
  t[i] = 0;
  for (j = 0; j < i; j++) if (a[j] < a[i]) t[i]++;
 } 
 for (i = 0; i < 9; i++) s = s + t[i] * Fact[i];
 return s;
}
void Expand(Heap_Node State)
{
 Heap_Node NewState;
 int x,y;
 int a[3][3];
 x = State.x;
 y = State.y;
 a = State.a;
 for (int i = 0; i < 4; i++)
 {
  if (x+dx[i]>=0 && x+dx[i]<3 && y+dy[i]>=0 && y+dy[i]<3)
  {
   NewState.a = a;
   NewState.g = State.g + 1;
   NewState.a[x][y] = a[x+dx[i]][y+dy[i]];
   NewState.a[x+dx[i]][y+dy[i]]=0;
   NewState.x = x + dx[i];
   NewState.y = y + dy[i];
   NewState.h = Value(NewState);
   NewState.father = &State;
   if (TableTwo[Hash(NewState)])
   {
    TableOne.push(NewState);
    TableTwo[Hash(State)] = false;
   }
  }
 }
}

bool IsAnswer(Heap_Node State)
{
 for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
       if (State.a[i][j] != Target.a[i][j]) return false;
 return true;
}
 
void print(Heap_Node *State)
{
 while(State->father != NULL)
 {
  for (int i = 0; i < 3; i++)
  {
   for (int j = 0; j < 3; j++) ouf<<State->a[i][j]<<' ';
   ouf<<endl;
  }
  State = State->father;
 }
}
 
void AStar()
{
 bool Ok; 
 Ok = false;
 Heap_Node State;
 TableOne.push(Strat);
 while (!Ok && !TableOne.empty())
 {
  State = TableOne.top();
  TableOne.pop();
  if (IsAnswer(State))
  {
   Ok = true;
   cout<<"Number of times:"<<State.g<<endl;
  }
  else Expand(State);
 };
 if (!Ok) ouf<<"No Answer!"<<endl;
}

int main ()
{
 for (int i = 0; i < 362879; i++) TableTwo[i] = true;
 for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
  {
   inf>>Strat.a[i][j];
   if (Strat.a[i][j] == 0)
   {
    Strat.x = i;
    Strat.y = j;
   }
  }
 Strat.father = NULL;
 Strat.g = 0;
 Strat.h = Value(Strat);
 for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
  {
   inf>>Target.a[i][j];
  }
 Change(Target);
 AStar(); 
}

program num8or15;

{$mode objfpc}{$H+}

uses
  Classes, SysUtils
  { add your units here };
const
  num=8;
type
  node=string[num+1];
var
  list:array[1..50000] of node;
  f:array[1..50000] of integer;
  st,tt:node;
  nodestr:string[num+1];
  i,j,k,l,s,t,p:integer;
 
  function exchange(s:string;i,j:integer):string[num+1];
  var
    t:string;
  begin
    t:=copy(s,j,1);
    delete(s,i,1);
    insert(t,s,i);
    delete(s,j,1);
    insert('0',s,j);
    result:=s;
  end;
 
  function canchange(i,j:byte):boolean;
  var
    x1,y1,x2,y2:byte;
  begin
    canchange:=true;
    y1:=i mod 3; if y1=0 then y1:=3;
    x1:=(i-y1) div 3+1;
    y2:=j mod 3; if y2=0 then y2:=3;
    x2:=(j-y2) div 3+1;
    if(abs(x1-x2)+abs(y1-y2)<>1) then canchange:=false;
  end;
 
  procedure print(x:integer);
  begin
    if x=1 then
      for k:=1 to 3 do begin
        for l:=1 to 3 do write(copy(st,(k-1)*3+l,1),' ');
        writeln;
      end
    else begin
      print(f[x]);
      writeln;
      for k:=1 to 3 do begin
        for l:=1 to 3 do write(copy(list[x],(k-1)*3+l,1),' ');
        writeln;
      end;
    end;
  end;
 
begin
  assign(output,'num8or15.out'); rewrite(output);
  st:=''; tt:='';
  for i:=1 to 3 do begin
    for j:=1 to 3 do begin read(k); st:=st+chr(k+48); end;
    readln;
  end;
  for i:=1 to 3 do begin
    for j:=1 to 3 do begin read(k); tt:=tt+chr(k+48); end;
    readln;
  end;

  s:=0; t:=1; list[1]:=st; f[1]:=0;
  repeat
    inc(s);
    if list[s]=tt then begin print(s); break; end;
    p:=pos('0',list[s]);
    for i:=1 to 4 do
      if((p+i*2-5)>=1)and((p+i*2-5)<=9)and(canchange(p,p+i*2-5))then begin
        nodestr:=exchange(list[s],p,p+i*2-5);
        for j:=1 to t do if list[j]=nodestr then break;
        inc(t);
        list[t]:=nodestr;
        f[t]:=s;
      end;
  until s=t;
  if(s=t) then writeln('No answer!!!');
  close(output);
end.