fork download
copy 
  1. #include <stdio.h>
  2.  
  3. char	*name[] = {
  4. 	"",
  5. 	"01:北海道", 
  6. 	"02:青森県", "03:岩手県", "04:宮城県", "05:秋田県", "06:山形県", "07:福島県",
  7. 	"08:茨城県", "09:栃木県", "10:群馬県", "11:埼玉県", "12:千葉県", "13:東京都", "14:神奈川県",
  8. 	"15:新潟県", "16:富山県", "17:石川県", "18:福井県", "19:山梨県", "20:長野県",
  9. 	"21:岐阜県", "22:静岡県", "23:愛知県", "24:三重県",
  10. 	"25:滋賀県", "26:京都府", "27:大阪府", "28:兵庫県", "29:奈良県", "30:和歌山県",
  11. 	"31:鳥取県", "32:島根県", "33:岡山県", "34:広島県", "35:山口県",
  12. 	"36:徳島県", "37:香川県", "38:愛媛県", "39:高知県",
  13. 	"40:福岡県", "41:佐賀県", "42:長崎県", "43:熊本県", "44:大分県", "45:宮崎県", "46:鹿児島県", "47:沖縄県",
  14. };
  15.  
  16.     int connect[][10] =
  17.     {
  18. 		{ 1, 2}, // 1:北海道
  19. 		{ 2, 1, 3, 5}, // 2:青森県
  20. 		{ 3, 2, 4, 5}, // 3:岩手県
  21. 		{ 4, 3, 6, 7}, // 4:宮城県
  22. 		{ 5, 2, 3, 6}, // 5:秋田県
  23. 		{ 6, 3, 4, 5, 7,15}, // 6:山形県
  24. 		{ 7, 4, 6, 8, 9,10,15}, // 7:福島県
  25. 		{ 8, 6, 9,11,12}, // 8:茨城県
  26. 		{ 9, 7, 8,10}, // 9:栃木県
  27. 		{10, 7, 9,11,15,20}, // 10:群馬県
  28. 		{11, 8,10,12,13,20,19}, // 11:埼玉県
  29. 		{12, 8,11,13,14}, // 12:千葉県
  30. 		{13,11,12,14,19}, // 13:東京都
  31. 		{14,12,13,22,19}, // 14:神奈川県
  32. 		{15,16,20, 6, 7,10}, // 15:新潟県
  33. 		{16,15,17,20,21}, // 16:富山県
  34. 		{17,16,18,21}, // 17:石川県
  35. 		{18,16,17,21,26}, // 18:福井県
  36. 		{19,11,13,14,22,20,21}, // 19:山梨県
  37. 		{20,15,16,19,21,22,23}, // 20:長野県
  38. 		{21,16,17,18,20,22,23}, // 21:岐阜県
  39. 		{22,14,19,20,21,23}, // 22:静岡県
  40. 		{23,21,22,24,25,29}, // 23:愛知県
  41. 		{24,23,30,29}, // 24:三重県
  42. 		{25,26,29,18,21}, // 25:滋賀県
  43. 		{26,25,27,29}, // 26:京都府
  44. 		{27,26,28,29,30}, // 27:大阪府
  45. 		{28,27,26,33,31,36}, // 28:兵庫県
  46. 		{29,25,26,27,30,23,24}, // 29:奈良県
  47. 		{30,27,29,24}, // 30:和歌山県
  48. 		{31,32,33,34,28}, // 31:鳥取県
  49. 		{32,31,33,34,35}, // 32:島根県
  50. 		{33,31,32,34,37,28}, // 33:岡山県
  51. 		{34,31,32,33,35,38}, // 34:広島県
  52. 		{35,32,34,40}, // 35:山口県
  53. 		{36,37,39,28}, // 36:徳島県
  54. 		{37,36,38,39,33}, // 37:香川県
  55. 		{38,36,37,39,34}, // 38:愛媛県
  56. 		{39,36,37,38}, // 39:高知県
  57. 		{40,41,43,44,35}, // 40:福岡県
  58. 		{41,40,42,43}, // 41:佐賀県
  59. 		{42,41}, // 42:長崎県
  60. 		{43,40,41,44,45,46}, // 43:熊本県
  61. 		{44,40,43,45}, // 44:大分県
  62. 		{45,43,44,46}, // 45:宮崎県
  63. 		{46,43,45,47}, // 46:鹿児島県
  64. 		{47,46}, // 47:沖縄県
  65. 	{-1}
  66.     };
  67.  
  68. int neigh[48][48];
  69. void travel(int ken);
  70. int main()
  71. {
  72. 	int	i,j,k,ken,flag;
  73.  
  74. 	/* 県ごとの隣接テーブルを作る */
  75. 	for(i=0;connect[i][0] != -1;i++) {
  76. 		ken = connect[i][0];
  77. 		for(j=1;j<10;j++) {
  78. 			if(connect[i][j]){
  79. 				neigh[ken][connect[i][j]] = 1;
  80. 				neigh[connect[i][j]][ken] = 1;
  81. 			}
  82. 		}
  83. 	}
  84.  
  85. 	travel(47);			/* 沖縄から */
  86. 	return 0;
  87. }
  88.  
  89. char	visited[48];
  90. char	path[100];
  91. int	pass = 0;
  92.  
  93. void travel(int ken)
  94. {
  95. 	int	i,next,f;
  96.  
  97. 	if(ken == 47 && pass > 0) {
  98. 		printf("==== result ====\n");
  99. 		printf("%s ", name[47]);
  100. 		for(i=0;i<pass;i++) {
  101. 			printf("-> %s", name[path[i]]);
  102. 		}
  103. 		exit(0);
  104. 	}
  105.  
  106. 	/* 隣接県を全部試す */
  107. 	for(next=1; next<48; next++) {
  108. 		if(neigh[ken][next] == 0) continue;
  109.  
  110. 		if(visited[next] >= 2) continue;
  111. 		visited[next]++;
  112. 		path[pass++] = next;
  113. 		travel(next);
  114. 		visited[next]--;
  115. 		pass -= 1;
  116. 	}
  117. }
  118.  
  119.  
Success #stdin #stdout 0s 2256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
==== result ====
47:沖縄県 -> 46:鹿児島県-> 43:熊本県-> 40:福岡県-> 35:山口県-> 32:島根県-> 31:鳥取県-> 28:兵庫県-> 26:京都府-> 18:福井県-> 16:富山県-> 15:新潟県-> 06:山形県-> 03:岩手県-> 02:青森県-> 01:北海道-> 02:青森県-> 03:岩手県-> 04:宮城県-> 06:山形県-> 04:宮城県-> 07:福島県-> 08:茨城県-> 07:福島県-> 08:茨城県-> 09:栃木県-> 10:群馬県-> 09:栃木県-> 10:群馬県-> 11:埼玉県-> 12:千葉県-> 11:埼玉県-> 12:千葉県-> 13:東京都-> 14:神奈川県-> 13:東京都-> 14:神奈川県-> 19:山梨県-> 20:長野県-> 15:新潟県-> 16:富山県-> 17:石川県-> 18:福井県-> 17:石川県-> 21:岐阜県-> 19:山梨県-> 20:長野県-> 21:岐阜県-> 22:静岡県-> 23:愛知県-> 22:静岡県-> 23:愛知県-> 24:三重県-> 29:奈良県-> 24:三重県-> 29:奈良県-> 25:滋賀県-> 26:京都府-> 27:大阪府-> 28:兵庫県-> 31:鳥取県-> 32:島根県-> 33:岡山県-> 34:広島県-> 33:岡山県-> 34:広島県-> 35:山口県-> 40:福岡県-> 41:佐賀県-> 42:長崎県-> 41:佐賀県-> 43:熊本県-> 44:大分県-> 45:宮崎県-> 44:大分県-> 45:宮崎県-> 46:鹿児島県-> 47:沖縄県
https://ideone.com/APGYLT
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!