fork(42) download
copy 
  1. /* ==================================================================================================================
  2.  * CodeIQ
  3.  *
  4.  * K_Yaguchi
  5.  * 2016.11.05
  6.  ================================================================================================================== */
  7.  
  8. #include <stdio.h>
  9. //#include <ctype.h>
  10. //#include <conio.h>
  11.  
  12.  
  13. //////////////////////////////////////////////////
  14. //【実力判定：Sランク】まっすぐ行こう　 スキルチェック部さんの問題に挑戦中！
  15. //https://c...content-available-to-author-only...q.jp/challenge/2516
  16. #define MAXNODE 64 // 最大ノード
  17.  
  18. // ノード
  19. typedef struct _node {
  20. 	char isnode; // 自身のノードの種類 '.' or '#'
  21. 	int isgoal;  // 1=ゴール
  22. 	int cost   ; // 移動コスト -1=初期値
  23. } NODE;
  24.  
  25. // 探索用データ
  26. typedef struct _trac {
  27. 	int cost; // 曲がった数
  28. 	int vect; // 探索方向 0=初期値 1=top 2=bottom 3=left 4=right
  29. 	int row;  // 探索すべき行
  30. 	int col;  // 探索すべき列
  31. } TRAC;
  32.  
  33. // 探索
  34. // 戻り値：ゴールした=1
  35. static int route(NODE node[MAXNODE][MAXNODE], int m, int n, TRAC* trac, int* goal, int* mincost)
  36. {
  37. 	int r=0,c=0;
  38. 	int ret=0;
  39. 	TRAC t={0};
  40. 	int istop=0,isbottom=0,isleft=0,isright=0; // 次に移動できるノード
  41. 	int i=0;
  42. 	int vect=0;
  43.  
  44. 	r = trac->row;
  45. 	c = trac->col;
  46. 	vect = trac->vect;
  47.  
  48. 	if( node[r][c].cost < 0 || node[r][c].cost > trac->cost)
  49. 		node[r][c].cost = trac->cost;
  50.  
  51. 	// ゴール
  52. 	if( node[r][c].isgoal )
  53. 	{
  54. 		if( *mincost < 0 || trac->cost < *mincost )
  55. 			*mincost = trac->cost;
  56. 		(*goal)++;
  57. /*
  58. 		for(int y=0;y<m;y++)
  59. 		{
  60. 			printf("\n");
  61. 			for(int x=0;x<n;x++)
  62. 			{
  63. 				if( node[y][x].cost >= 0 )
  64. 					printf("%d", node[y][x].cost);
  65. 				else
  66. 					printf("%c", node[y][x].isnode);
  67. 			}
  68. 		}
  69. */
  70. 		return 1;
  71. 	}
  72.  
  73. 	// 次に移動できるノード
  74. 	istop    = (int)( r > 0 && node[r-1][c].isnode == '.' && trac->vect != 2 && (node[r-1][c].cost < 0 || node[r-1][c].cost > trac->cost) );
  75. 	isbottom = (int)( r < m && node[r+1][c].isnode == '.' && trac->vect != 1 && (node[r+1][c].cost < 0 || node[r+1][c].cost > trac->cost) );
  76. 	isleft   = (int)( c > 0 && node[r][c-1].isnode == '.' && trac->vect != 4 && (node[r][c-1].cost < 0 || node[r][c-1].cost > trac->cost) );
  77. 	isright  = (int)( c < n && node[r][c+1].isnode == '.' && trac->vect != 3 && (node[r][c+1].cost < 0 || node[r][c+1].cost > trac->cost) );
  78.  
  79. 	for(i=0; i<4; i++)
  80. 	{
  81. 		if( vect == 0 || vect == 1 )
  82. 		{
  83. 			// 上へ
  84. 			if( istop )
  85. 			{
  86. 				t = *trac;
  87. 				if( t.vect != 0 && t.vect != 1)
  88. 					t.cost++;
  89. 				t.vect = 1;
  90. 				t.row--;
  91. 				ret = route(node, m, n, &t, goal, mincost);
  92. 			}
  93. 			vect = 2;
  94. 		}
  95. 		else if( vect == 2 )
  96. 		{
  97. 			// 下へ
  98. 			if( isbottom )
  99. 			{
  100. 				t = *trac;
  101. 				if( t.vect != 0 && t.vect != 2)
  102. 					t.cost++;
  103. 				t.vect = 2;
  104. 				t.row++;
  105. 				ret = route(node, m, n, &t, goal, mincost);
  106. 			}
  107. 			vect = 3;
  108. 		}
  109. 		else if( vect == 3 )
  110. 		{
  111. 			// 左へ
  112. 			if( isleft )
  113. 			{
  114. 				t = *trac;
  115. 				if( t.vect != 0 && t.vect != 3)
  116. 					t.cost++;
  117. 				t.vect = 3;
  118. 				t.col--;
  119. 				ret = route(node, m, n, &t, goal, mincost);
  120. 			}
  121. 			vect = 4;
  122. 		}
  123. 		else if( vect == 4 )
  124. 		{
  125. 			// 右へ
  126. 			if( isright )
  127. 			{
  128. 				t = *trac;
  129. 				if( t.vect != 0 && t.vect != 4)
  130. 					t.cost++;
  131. 				t.vect = 4;
  132. 				t.col++;
  133. 				ret = route(node, m, n, &t, goal, mincost);
  134. 			}
  135. 			vect = 1;
  136. 		}
  137. 	}
  138.  
  139. 	return ret;
  140. }
  141.  
  142. int main(void)
  143. {
  144. 	int m=0,n=0;
  145. 	int r=0,c=0;
  146. 	char line[MAXNODE+2]="";
  147. 	NODE node[MAXNODE][MAXNODE]={0};
  148. 	TRAC trac={0};
  149. 	int cost=-1;
  150. 	int goal=0;
  151.  
  152. 	// m=行数 n=マス数
  153. 	scanf("%d %d\n", &m, &n);
  154. 	for(r=0; r<m; r++)
  155. 	{
  156. 		fgets(line, sizeof(line), stdin);
  157. 		for(c=0; c<n; c++)
  158. 		{
  159. 			node[r][c].isnode = line[c];
  160. 			node[r][c].cost   = -1;
  161. 		}
  162. 	}
  163.  
  164. 	trac.row = m-1; // スタート位置
  165. 	trac.col = n-1;
  166. 	node[0][0].isgoal = 1; // ゴール位置
  167.  
  168. 	// 探索
  169. 	route(node, m, n, &trac, &goal, &cost);
  170.  
  171. 	printf("%d\n", cost);
  172. 	printf("経路数:%d 最小コスト:%d\n", goal, cost);
  173. //	getch();
  174. 	return 0;
  175. }
  176.  
Success #stdin #stdout 0.03s 2164KB
comments (?)
stdin
copy 
64 64
.......#...........#.#....#..#....###...#.##..............#.....
#....#.....#...#......###........##...#.............##..#.......
#....#..##..#......##.#.#....#.##...#........#.....#.#........#.
..#.##.....#.........##.........#..#..#..###.#.......##......#..
..#....##...##...#...##..........#..#...........##.#.###.#...#.#
.#..##....#..##..........#.#.#....#...#..#.##.....#.##.........#
..#.....#....##....#.#.#...#....#...#...##....###..#....#.#..#..
.#.#....#.#.......##.#.....#...............#.#####.......#...#.#
..#.#.##.#....#.#.#.#.......#...#......#.......#..#....#..#.#...
.##...........##........#...#.......#.....#...#.....#..#.......#
...#.......#.....#.###..............#..#..#...##.#..#.#.#.###...
........#.#..#.##.....#.#..#...#####....#.......#.##.#.##.#.....
.#...##.....#.#.......##......#.....#...#...#....#.......##....#
...................#.#....#.#.....####...##.....................
#....##......##.#...#..#.......##.#...#..#..#...........#.#.....
####.....................#.....#...#.#...#..#........#..........
.......#...#..........#....#...........#...#.##..#...###..#....#
...#.....##.##...#............#........#.#.......#.....##.#...#.
#..##.....#..#.#...#.#.#...#...#.##.#...#...#....#.........##...
.....#.#.#.......#....#.....#....#..#....####......#...#........
..#..#...........#...#....#...#...#.#..............#....#....##.
.#.#.#.........#...........##....#..............##.....###...#..
............#....#..##........##..#....#...##..#..#....#....#..#
###.....#..#....#.#.##.....#...#..##....##............#.#..#.#.#
......#...#....#....#.....#....##..#.###....###..#....#........#
..#.##......##.#.##.#...#......######........##.#....##.#.#.#..#
...#...#........#.....####.#.##.#....#..##...#.......#..........
........#..#..#.#.....#......#...#..#..#......#....##.#.#..###..
#....##.......#...#...#......#.#.....#..#..##...#...#...........
#..#.......#.......#.##.#...#..#.......#.#......#.##............
...#...........###......#.......#...........#..........#.......#
......#...........#.....#..##........#...#...#....##.#.#....#...
....##...#...#.#.....###.#.#.#.....#..#.#.#...#....#.#........#.
.#.#..#..##...........#.....##.##.#....##....##...#....#..#.##..
#.........#.......##...........#......##...##.#.##.##.....##....
...##....##.##.#.###.#....#.....##......#..#..........#.##.....#
........##..####.......#......##.....#...##.....#...........#...
.#.#....##..#..#..##.....#.......##............#....#...#..#.##.
.........#.....#.....###....#........#...#....##..#.....#...#...
...#...#...##......#...###....#.....#...#.#..##..#......#..#....
..........#.#...#.##......#...##.##.............#..##.....##.#..
.................##...#.....#.#.##.....#.......#.....#..#.....#.
.....#..................#...#....#.#.#...#......#...##..#.#....#
..#....#.#.#.#...#.....#......##...............####....##.......
#..#.#..#.......#.........#......#................#...#.###..##.
.##..........#.......#..#....##........####.....#...#.#.#.#....#
...#.##.#..##.......#.....##......#.#.....#.#.........#.#.#.....
..#.......##.......#...................#..#..#.....#.........##.
##...###....#...#..#...#........#..#.#.......##.....#....#..#...
...##..#.........##...#.........#..#.#.#......#.......#..#..##.#
.#...#....#.#.....#....#............#.#...#...#..#......#.##....
........#...##..#.#.#.....#.#.#......#.##.............#.###.....
#....#.#..#....#..#.##........#........#.....#.#.#....#..#...###
..#......#.#.........#.#....#.#.....#....##.#..#.##.....#.#.....
.##......#...#......#.#...#.....##...........#........#.........
...#...##.#...#.#....#.......###....#.......#...#.#....#.####.#.
.#...#.......#...#.....##.#..##.................#.....##.#..#...
...#..#.................#....#.##........#....#.....##..#..##.#.
#..#.......#.#.#.#.#..###........#.....#.#..#...#...##.#....#...
###.#.#.#.#..#.........#.....#.........#.#..##.#.........#...##.
#.....##.#....#.##.##.#..##.##...##...##.##...#.#..#.##.#.....#.
.##..#..#...#..##.#.##......#.#..........#...........#.......#..
..#.......#...................##.......#.#..#..#......#...#.....
......#.#..#.......##...#.##.....#..##..#..#........#.#.....#.#.
stdout
copy 
23
経路数:19 最小コスト:23
https://ideone.com/pfoy7z
language:
C (gcc 8.3)
created:
8 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!