• 字符串 13.激光镜像

    【问题描述】

          有一个 n×m 的网格，其中包含一些实心单元和一些空心单元。网格左上角的坐标为(1, 1)，而右下角的坐标为(n, m)。其中有 k 个实心单元，而其他的则是空心的。这时从坐标为( xs，ys )的单元中心向四个对角方向之一（也就是东北、西北、东南和西南）的方向发射一个激光束，如果激光束遇到实心单元或网格边缘则形成反射或折射。方式如下（入射角度为NE为例）：

           一段时间后，激光束将进入一个死循环，计算在进入死循环之前激光束穿越至少一次的空单元格总数，穿越是指穿过单元中心。

     

    【输入形式】

           输入的第一行包含三个整数 n、m 和 k (1≤n、m≤1000, 0≤k≤1000)。接下来的 k 行每行包含两个整数 xi 和 yi (1≤xi≤n，1≤yi≤m)，表示第 i 个实心单元的位置。

           最后一行包含两个整数xs 、 ys (1≤xs≤n，1≤ys≤m)以及激光发射方向，分别用"NE"、"NW"、"SE"、"SW"代表东北、西北、东南、西南方向。

    【输出形式】

           输出仅有一行一个数字，表示激光束进入死循环之前所穿越过至少一次的空心单元格的总数。
    【样例输入1】

    3 3 0
1 2 SW

    【样例输出1】

    6

    【样例输入2】

    7 5 3
3 3
4 3
5 3
2 1 SE

    【样例输出2】

    14

    【提示】

         可以将 n×m 的网格扩大为(n+2)×(m+2)，其中的所有:

                         (0, i), i=0,1,...,m+1单元

                         (j, 0)，j=0,1, ..., n+1单元

                         (n+1, i), i=0,1,...,m+1单元

                         (j, m+1), j=0, 1,...,n+1单元

        都可以看做为实心单元。

    【评分标准】274E

    浅浅发个超时的...

    看看有无大佬能帮忙优化一下

    1. #include//注：此题数组下标从1开始而不是0，便于计数 
    2. using namespace std;
    3. int main()
    4. {
    5. 	string direction;
    6. 	int n,m,k;
    7. 	int xs,ys;
    8. 	cin>>n>>m>>k;
    9. 	int Black[n+1][m+1];//记录黑色方块的位置 
    10. 	int Cnt[n+1][m+1];//记录激光经过的方块 
    11. 	int arr[k][2];
    12. 	fill(Black[0],Black[0]+(n+1)*(m+1),0);
    13. 	fill(Cnt[0],Cnt[0]+(n+1)*(m+1),0);//将Black和Cnt数组全部归零 
    14. 	for(int i=1;i<=k;i++)
    15. 	{
    16. 		cin>>arr[i][0]>>arr[i][1];
    17. 		Black[arr[i][0]][arr[i][1]]++;
    18. 	}
    19. 	cin>>xs>>ys>>direction;
    20. 	Cnt[xs][ys]=1;//先标注起点 
    21. 	int Startx=xs,Starty=ys;
    22. 	int flagx=Startx,flagy=Starty;
    23. 	string flagd=direction;
    24. 	while(1)
    25. 	{
    26. 	//一.-------------------------------------------------------------------- 
    27. 	if(direction=="NE")//先确定方向 //皆为单步操作 
    28. 	{
    29. 		if(Startx>1&&Starty//没到边缘
    30. 		{
    31. 			if(Black[Startx-1][Starty+1]==1)//斜对角是黑色 
    32. 			{
    33. 				if((Black[Startx][Starty+1]==1&&Black[Startx-1][Starty]==1)||(Black[Startx][Starty+1]!=1&&Black[Startx-1][Starty]!=1))
    34. 				{
    35. 					direction=="SW";
    36. 				}
    37. 				else if(Black[Startx][Starty+1]==1&&Black[Startx-1][Starty]!=1)
    38. 				{
    39. 					direction=="NW";
    40. 					Startx--;
    41. 					Cnt[Startx][Starty]++; 
    42. 				}
    43. 				else if(Black[Startx][Starty+1]!=1&&Black[Startx-1][Starty]==1)
    44. 				{
    45. 					direction=="SE";
    46. 					Starty++;
    47. 					Cnt[Startx][Starty]++; 
    48. 				}
    49. 			}
    50. 			else if(Black[Startx-1][Starty+1]!=1)//斜对角为白块
    51. 			{
    52. 				Startx--;
    53. 				Starty++;
    54. 				Cnt[Startx][Starty]++;
    55. 			} 
    56. 		}
    57. 		else if(Startx==1&&Starty//碰到上边缘 
    58. 		{
    59. 			direction="SE";
    60. 			Starty++;
    61. 			Cnt[Startx][Starty]++;
    62. 		}
    63. 		else if(Startx>1&&Starty==m)//碰到右边缘 
    64. 		{
    65. 			direction="NW";
    66. 			Startx--;
    67. 			Cnt[Startx][Starty]++;
    68. 		}
    69. 		else if(Startx==1&&Starty==m)//碰到右上方拐角 
    70. 		{
    71. 			direction="SW";
    72. 		}
    73. 	}
    74. 	//--------------------------------------------------------------------- 
    75. 	//二.-------------------------------------------------------------------- 
    76. 	else if(direction=="SE")//先确定方向 //皆为单步操作 
    77. 	{
    78. 		if(Startx//没到边缘
    79. 		{
    80. 			if(Black[Startx+1][Starty+1]==1)//斜对角是黑色 
    81. 			{
    82. 				if((Black[Startx][Starty+1]==1&&Black[Startx+1][Starty]==1)||(Black[Startx][Starty+1]!=1&&Black[Startx+1][Starty]!=1))
    83. 				{
    84. 					direction=="NW";
    85. 				}
    86. 				else if(Black[Startx][Starty+1]==1&&Black[Startx+1][Starty]!=1)
    87. 				{
    88. 					direction=="SW";
    89. 					Startx++;
    90. 					Cnt[Startx][Starty]++; 
    91. 				}
    92. 				else if(Black[Startx][Starty+1]!=1&&Black[Startx+1][Starty]==1)
    93. 				{
    94. 					direction=="NE";
    95. 					Starty++;
    96. 					Cnt[Startx][Starty]++; 
    97. 				}
    98. 			}
    99. 			else if(Black[Startx+1][Starty+1]!=1)//斜对角为白块
    100. 			{
    101. 				Startx++;
    102. 				Starty++;
    103. 				Cnt[Startx][Starty]++;
    104. 			} 
    105. 		}
    106. 		else if(Startx//碰到右边缘 
    107. 		{
    108. 			direction="SW";
    109. 			Startx++;
    110. 			Cnt[Startx][Starty]++;
    111. 		}
    112. 		else if(Startx==n&&Starty//碰到下边缘 
    113. 		{
    114. 			direction="NE";
    115. 			Starty++;
    116. 			Cnt[Startx][Starty]++;
    117. 		}
    118. 		else if(Startx==n&&Starty==m)//碰到右下方拐角 
    119. 		{
    120. 			direction="NW";
    121. 		}
    122. 	}
    123. 	//--------------------------------------------------------------------- 
    124. 	//三.-------------------------------------------------------------------- 
    125. 	else if(direction=="NW")//先确定方向 //皆为单步操作 
    126. 	{
    127. 		if(Startx>1&&Starty>1)//没到边缘
    128. 		{
    129. 			if(Black[Startx-1][Starty-1]==1)//斜对角是黑色 
    130. 			{
    131. 				if((Black[Startx][Starty-1]==1&&Black[Startx-1][Starty]==1)||(Black[Startx][Starty-1]!=1&&Black[Startx-1][Starty]!=1))
    132. 				{
    133. 					direction=="SE";
    134. 				}
    135. 				else if(Black[Startx][Starty-1]==1&&Black[Startx-1][Starty]!=1)
    136. 				{
    137. 					direction=="NE";
    138. 					Startx--;
    139. 					Cnt[Startx][Starty]++; 
    140. 				}
    141. 				else if(Black[Startx][Starty-1]!=1&&Black[Startx-1][Starty]==1)
    142. 				{
    143. 					direction=="SW";
    144. 					Starty--;
    145. 					Cnt[Startx][Starty]++; 
    146. 				}
    147. 			}
    148. 			else if(Black[Startx-1][Starty-1]!=1)//斜对角为白块
    149. 			{
    150. 				Startx--;
    151. 				Starty--;
    152. 				Cnt[Startx][Starty]++;
    153. 			} 
    154. 		}
    155. 		else if(Startx>1&&Starty==1)//碰到左边缘 
    156. 		{
    157. 			direction="NE";
    158. 			Startx--;
    159. 			Cnt[Startx][Starty]++;
    160. 		}
    161. 		else if(Startx==1&&Starty>1)//碰到上边缘 
    162. 		{
    163. 			direction="SW";
    164. 			Starty--;
    165. 			Cnt[Startx][Starty]++;
    166. 		}
    167. 		else if(Startx==1&&Starty==1)//碰到左上方拐角 
    168. 		{
    169. 			direction="SE";
    170. 		}
    171. 	}
    172. 	//--------------------------------------------------------------------- 
    173. 	//四.-------------------------------------------------------------------- 
    174. 	else if(direction=="SW")//先确定方向 //皆为单步操作 
    175. 	{
    176. 		if(Startx1)//没到边缘
    177. 		{
    178. 			if(Black[Startx+1][Starty-1]==1)//斜对角是黑色 
    179. 			{
    180. 				if((Black[Startx][Starty-1]==1&&Black[Startx+1][Starty]==1)||(Black[Startx][Starty-1]!=1&&Black[Startx+1][Starty]!=1))
    181. 				{
    182. 					direction=="NE";
    183. 				}
    184. 				else if(Black[Startx][Starty-1]==1&&Black[Startx+1][Starty]!=1)
    185. 				{
    186. 					direction=="SE";
    187. 					Startx++;
    188. 					Cnt[Startx][Starty]++; 
    189. 				}
    190. 				else if(Black[Startx][Starty-1]!=1&&Black[Startx+1][Starty]==1)
    191. 				{
    192. 					direction=="NW";
    193. 					Starty--;
    194. 					Cnt[Startx][Starty]++; 
    195. 				}
    196. 			}
    197. 			else if(Black[Startx+1][Starty-1]!=1)//斜对角为白块
    198. 			{
    199. 				Startx++;
    200. 				Starty--;
    201. 				Cnt[Startx][Starty]++;
    202. 			} 
    203. 		}
    204. 		else if(Startx==n&&Starty>1)//碰到下边缘 
    205. 		{
    206. 			direction="NW";
    207. 			Starty--;
    208. 			Cnt[Startx][Starty]++;
    209. 		}
    210. 		else if(Startx1)//碰到左边缘 
    211. 		{
    212. 			direction="SE";
    213. 			Startx++;
    214. 			Cnt[Startx][Starty]++;
    215. 		}
    216. 		else if(Startx==n&&Starty==1)//碰到左下方拐角 
    217. 		{
    218. 			direction="NE";
    219. 		}
    220. 	}
    221. 	//--------------------------------------------------------------------- 
    222. 		if(Startx==flagx&&Starty==flagy&&direction==flagd)
    223. 		{
    224. 			break; 
    225. 		}
    226. 	}
    227. 	int sum=0;
    228. 	for(int i=1;i<=n;i++)
    229. 	{
    230. 		for(int j=1;j<=m;j++)
    231. 		{
    232. 			if(Cnt[i][j]>0)
    233. 			{
    234. 				sum++;
    235. 			}
    236. 		}
    237. 	}
    238. 	cout<
    239. 	system("pause");
    240. 	return 0;
    241. }
  • 相关阅读:
    CKM3N 数据存表
    【Godot】给不规则的 TileMap 划分子区域块部分代码
    生命周期成本VE——五十铃汽车
    前端实训DAY-5——移动适配：rem
    如何在Proteus进行STM32F103C8T6模拟以及keil5开发
    Linux文件管理知识:文本处理
    类与对象(十二)----对象的创建流程
    python毕业设计作品基于django框架 多用户商城平台系统毕设成品（5）任务书
    web前端期末大作业 HTML游戏资讯网页设计制作 简单静态HTML网页作品 DW游戏资讯网页作业成品 游戏网站模板
    高校社团管理系统jsp和javabean开发
  • 原文地址：https://blog.csdn.net/obstacle19/article/details/127641532