#include <stdio.h>
char *name[] = {
"",
"01:北海道",
"02:青森県", "03:岩手県", "04:宮城県", "05:秋田県", "06:山形県", "07:福島県",
"08:茨城県", "09:栃木県", "10:群馬県", "11:埼玉県", "12:千葉県", "13:東京都", "14:神奈川県",
"15:新潟県", "16:富山県", "17:石川県", "18:福井県", "19:山梨県", "20:長野県",
"21:岐阜県", "22:静岡県", "23:愛知県", "24:三重県",
"25:滋賀県", "26:京都府", "27:大阪府", "28:兵庫県", "29:奈良県", "30:和歌山県",
"31:鳥取県", "32:島根県", "33:岡山県", "34:広島県", "35:山口県",
"36:徳島県", "37:香川県", "38:愛媛県", "39:高知県",
"40:福岡県", "41:佐賀県", "42:長崎県", "43:熊本県", "44:大分県", "45:宮崎県", "46:鹿児島県", "47:沖縄県",
};
int connect[][1+6] =
{
{ 1, 2}, // 1:北海道
{ 2, 1, 3, 5}, // 2:青森県
{ 3, 2, 4, 5}, // 3:岩手県
{ 4, 3, 6, 7}, // 4:宮城県
{ 5, 2, 3, 6}, // 5:秋田県
{ 6, 3, 4, 5, 7,15}, // 6:山形県
{ 7, 4, 6, 8, 9,10,15}, // 7:福島県
{ 8, 6, 9,11,12}, // 8:茨城県
{ 9, 7, 8,10}, // 9:栃木県
{10, 7, 9,11,15,20}, // 10:群馬県
{11, 8,10,12,13,20,19}, // 11:埼玉県
{12, 8,11,13,14}, // 12:千葉県
{13,11,12,14,19}, // 13:東京都
{14,12,13,22,19}, // 14:神奈川県
{15,16,20, 6, 7,10}, // 15:新潟県
{16,15,17,20,21}, // 16:富山県
{17,16,18,21}, // 17:石川県
{18,16,17,21,26}, // 18:福井県
{19,11,13,14,22,20,21}, // 19:山梨県
{20,15,16,19,21,22,23}, // 20:長野県
{21,16,17,18,20,22,23}, // 21:岐阜県
{22,14,19,20,21,23}, // 22:静岡県
{23,21,22,24,25,29}, // 23:愛知県
{24,23,30,29}, // 24:三重県
{25,26,29,18,21}, // 25:滋賀県
{26,25,27,29}, // 26:京都府
{27,26,28,29,30}, // 27:大阪府
{28,27,26,33,31,36}, // 28:兵庫県
{29,25,26,27,30,23,24}, // 29:奈良県
{30,27,29,24}, // 30:和歌山県
{31,32,33,34,28}, // 31:鳥取県
{32,31,33,34,35}, // 32:島根県
{33,31,32,34,37,28}, // 33:岡山県
{34,31,32,33,35,38}, // 34:広島県
{35,32,34,40}, // 35:山口県
{36,37,39,28}, // 36:徳島県
{37,36,38,39,33}, // 37:香川県
{38,36,37,39,34}, // 38:愛媛県
{39,36,37,38}, // 39:高知県
{40,41,43,44,35}, // 40:福岡県
{41,40,42,43}, // 41:佐賀県
{42,41}, // 42:長崎県
{43,40,41,44,45,46}, // 43:熊本県
{44,40,43,45}, // 44:大分県
{45,43,44,46}, // 45:宮崎県
{46,43,45,47}, // 46:鹿児島県
{47,46}, // 47:沖縄県
{-1}
};
int neigh[48][48];
void travel(int ken);
int main()
{
int i,j,k,ken,flag;
/* 県ごとの隣接テーブルを作る */
for(i=0;connect[i][0] != -1;i++) {
ken = connect[i][0];
for(j=1;j<10;j++) {
if(connect[i][j]){
neigh[ken][connect[i][j]] = 1;
neigh[connect[i][j]][ken] = 1;
}
}
}
travel(47); /* 沖縄から */
return 0;
}
char visited[48];
char path[100];
int pass = 0;
void travel(int ken)
{
int i,next,f;
if(ken == 47 && pass > 0) {
for(i=0;i<pass;i++) {
printf("-> %s", name
[path
[i
]]); }
}
/* 隣接県を全部試す */
for(next=1; next<48; next++) {
if(neigh[ken][next] == 0) continue;
if(visited[next] >= 2) continue;
visited[next]++;
path[pass++] = next;
travel(next);
visited[next]--;
pass -= 1;
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgpjaGFyCSpuYW1lW10gPSB7CgkiIiwKCSIwMTrljJfmtbfpgZMiLCAKCSIwMjrpnZLmo67nnIwiLCAiMDM65bKp5omL55yMIiwgIjA0OuWuruWfjuecjCIsICIwNTrnp4vnlLDnnIwiLCAiMDY65bGx5b2i55yMIiwgIjA3Ouemj+WztuecjCIsCgkiMDg66Iyo5Z+O55yMIiwgIjA5Ouagg+acqOecjCIsICIxMDrnvqTppqznnIwiLCAiMTE65Z+8546J55yMIiwgIjEyOuWNg+iRieecjCIsICIxMzrmnbHkuqzpg70iLCAiMTQ656We5aWI5bed55yMIiwKCSIxNTrmlrDmvZ/nnIwiLCAiMTY65a+M5bGx55yMIiwgIjE3Ouefs+W3neecjCIsICIxODrnpo/kupXnnIwiLCAiMTk65bGx5qKo55yMIiwgIjIwOumVt+mHjuecjCIsCgkiMjE65bKQ6Zic55yMIiwgIjIyOumdmeWyoeecjCIsICIyMzrmhJvnn6XnnIwiLCAiMjQ65LiJ6YeN55yMIiwKCSIyNTrmu4vos4DnnIwiLCAiMjY65Lqs6YO95bqcIiwgIjI3OuWkp+mYquW6nCIsICIyODrlhbXluqvnnIwiLCAiMjk65aWI6Imv55yMIiwgIjMwOuWSjOatjOWxseecjCIsCgkiMzE66bOl5Y+W55yMIiwgIjMyOuWztuagueecjCIsICIzMzrlsqHlsbHnnIwiLCAiMzQ65bqD5bO255yMIiwgIjM1OuWxseWPo+ecjCIsCgkiMzY65b6z5bO255yMIiwgIjM3OummmeW3neecjCIsICIzODrmhJvlqpvnnIwiLCAiMzk66auY55+l55yMIiwKCSI0MDrnpo/lsqHnnIwiLCAiNDE65L2Q6LOA55yMIiwgIjQyOumVt+W0juecjCIsICI0MzrnhormnKznnIwiLCAiNDQ65aSn5YiG55yMIiwgIjQ1OuWuruW0juecjCIsICI0Njrpub/lhZDls7bnnIwiLCAiNDc65rKW57iE55yMIiwKfTsKCiAgICBpbnQgY29ubmVjdFtdWzErNl0gPQogICAgewoJCXsgMSwgMn0sIC8vIDE65YyX5rW36YGTCgkJeyAyLCAxLCAzLCA1fSwgLy8gMjrpnZLmo67nnIwKCQl7IDMsIDIsIDQsIDV9LCAvLyAzOuWyqeaJi+ecjAoJCXsgNCwgMywgNiwgN30sIC8vIDQ65a6u5Z+O55yMCgkJeyA1LCAyLCAzLCA2fSwgLy8gNTrnp4vnlLDnnIwKCQl7IDYsIDMsIDQsIDUsIDcsMTV9LCAvLyA2OuWxseW9ouecjAoJCXsgNywgNCwgNiwgOCwgOSwxMCwxNX0sIC8vIDc656aP5bO255yMCgkJeyA4LCA2LCA5LDExLDEyfSwgLy8gODrojKjln47nnIwKCQl7IDksIDcsIDgsMTB9LCAvLyA5Ouagg+acqOecjAoJCXsxMCwgNywgOSwxMSwxNSwyMH0sIC8vIDEwOue+pOmmrOecjAoJCXsxMSwgOCwxMCwxMiwxMywyMCwxOX0sIC8vIDExOuWfvOeOieecjAoJCXsxMiwgOCwxMSwxMywxNH0sIC8vIDEyOuWNg+iRieecjAoJCXsxMywxMSwxMiwxNCwxOX0sIC8vIDEzOuadseS6rOmDvQoJCXsxNCwxMiwxMywyMiwxOX0sIC8vIDE0OuelnuWliOW3neecjAoJCXsxNSwxNiwyMCwgNiwgNywxMH0sIC8vIDE1OuaWsOa9n+ecjAoJCXsxNiwxNSwxNywyMCwyMX0sIC8vIDE2OuWvjOWxseecjAoJCXsxNywxNiwxOCwyMX0sIC8vIDE3Ouefs+W3neecjAoJCXsxOCwxNiwxNywyMSwyNn0sIC8vIDE4Ouemj+S6leecjAoJCXsxOSwxMSwxMywxNCwyMiwyMCwyMX0sIC8vIDE5OuWxseaiqOecjAoJCXsyMCwxNSwxNiwxOSwyMSwyMiwyM30sIC8vIDIwOumVt+mHjuecjAoJCXsyMSwxNiwxNywxOCwyMCwyMiwyM30sIC8vIDIxOuWykOmYnOecjAoJCXsyMiwxNCwxOSwyMCwyMSwyM30sIC8vIDIyOumdmeWyoeecjAoJCXsyMywyMSwyMiwyNCwyNSwyOX0sIC8vIDIzOuaEm+efpeecjAoJCXsyNCwyMywzMCwyOX0sIC8vIDI0OuS4iemHjeecjAoJCXsyNSwyNiwyOSwxOCwyMX0sIC8vIDI1Oua7i+izgOecjAoJCXsyNiwyNSwyNywyOX0sIC8vIDI2OuS6rOmDveW6nAoJCXsyNywyNiwyOCwyOSwzMH0sIC8vIDI3OuWkp+mYquW6nAoJCXsyOCwyNywyNiwzMywzMSwzNn0sIC8vIDI4OuWFteW6q+ecjAoJCXsyOSwyNSwyNiwyNywzMCwyMywyNH0sIC8vIDI5OuWliOiJr+ecjAoJCXszMCwyNywyOSwyNH0sIC8vIDMwOuWSjOatjOWxseecjAoJCXszMSwzMiwzMywzNCwyOH0sIC8vIDMxOumzpeWPluecjAoJCXszMiwzMSwzMywzNCwzNX0sIC8vIDMyOuWztuagueecjAoJCXszMywzMSwzMiwzNCwzNywyOH0sIC8vIDMzOuWyoeWxseecjAoJCXszNCwzMSwzMiwzMywzNSwzOH0sIC8vIDM0OuW6g+WztuecjAoJCXszNSwzMiwzNCw0MH0sIC8vIDM1OuWxseWPo+ecjAoJCXszNiwzNywzOSwyOH0sIC8vIDM2OuW+s+WztuecjAoJCXszNywzNiwzOCwzOSwzM30sIC8vIDM3OummmeW3neecjAoJCXszOCwzNiwzNywzOSwzNH0sIC8vIDM4OuaEm+Wqm+ecjAoJCXszOSwzNiwzNywzOH0sIC8vIDM5OumrmOefpeecjAoJCXs0MCw0MSw0Myw0NCwzNX0sIC8vIDQwOuemj+WyoeecjAoJCXs0MSw0MCw0Miw0M30sIC8vIDQxOuS9kOizgOecjAoJCXs0Miw0MX0sIC8vIDQyOumVt+W0juecjAoJCXs0Myw0MCw0MSw0NCw0NSw0Nn0sIC8vIDQzOueGiuacrOecjAoJCXs0NCw0MCw0Myw0NX0sIC8vIDQ0OuWkp+WIhuecjAoJCXs0NSw0Myw0NCw0Nn0sIC8vIDQ1OuWuruW0juecjAoJCXs0Niw0Myw0NSw0N30sIC8vIDQ2Oum5v+WFkOWztuecjAoJCXs0Nyw0Nn0sIC8vIDQ3Ouaylue4hOecjAoJey0xfQogICAgfTsKCmludCBuZWlnaFs0OF1bNDhdOwp2b2lkIHRyYXZlbChpbnQga2VuKTsKaW50IG1haW4oKQp7CglpbnQJaSxqLGssa2VuLGZsYWc7CgoJLyog55yM44GU44Go44Gu6Zqj5o6l44OG44O844OW44Or44KS5L2c44KLICovCglmb3IoaT0wO2Nvbm5lY3RbaV1bMF0gIT0gLTE7aSsrKSB7CgkJa2VuID0gY29ubmVjdFtpXVswXTsKCQlmb3Ioaj0xO2o8MTA7aisrKSB7CgkJCWlmKGNvbm5lY3RbaV1bal0pewoJCQkJbmVpZ2hba2VuXVtjb25uZWN0W2ldW2pdXSA9IDE7CgkJCQluZWlnaFtjb25uZWN0W2ldW2pdXVtrZW5dID0gMTsKCQkJfQoJCX0KCX0KCgl0cmF2ZWwoNDcpOwkJCS8qIOaylue4hOOBi+OCiSAqLwoJcmV0dXJuIDA7Cn0KCmNoYXIJdmlzaXRlZFs0OF07CmNoYXIJcGF0aFsxMDBdOwppbnQJcGFzcyA9IDA7Cgp2b2lkIHRyYXZlbChpbnQga2VuKQp7CglpbnQJaSxuZXh0LGY7CgoJaWYoa2VuID09IDQ3ICYmIHBhc3MgPiAwKSB7CgkJcHJpbnRmKCI9PT09IHJlc3VsdCA9PT09XG4iKTsKCQlwcmludGYoIiVzICIsIG5hbWVbNDddKTsKCQlmb3IoaT0wO2k8cGFzcztpKyspIHsKCQkJcHJpbnRmKCItPiAlcyIsIG5hbWVbcGF0aFtpXV0pOwoJCX0KCQlleGl0KDApOwoJfQoKCS8qIOmao+aOpeecjOOCkuWFqOmDqOippuOBmSAqLwoJZm9yKG5leHQ9MTsgbmV4dDw0ODsgbmV4dCsrKSB7CgkJaWYobmVpZ2hba2VuXVtuZXh0XSA9PSAwKSBjb250aW51ZTsKCgkJaWYodmlzaXRlZFtuZXh0XSA+PSAyKSBjb250aW51ZTsKCQl2aXNpdGVkW25leHRdKys7CgkJcGF0aFtwYXNzKytdID0gbmV4dDsKCQl0cmF2ZWwobmV4dCk7CgkJdmlzaXRlZFtuZXh0XS0tOwoJCXBhc3MgLT0gMTsKCX0KfQoK