Atcoder ABC339 B - Langton‘s Takahashi

本文主要是介绍Atcoder ABC339 B - Langton‘s Takahashi，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Langton’s Takahashi（兰顿的高桥）

时间限制：2s 内存限制：1024MB

【原题地址】

所有图片源自Atcoder，题目译文源自脚本Atcoder Better!

点击此处跳转至原题

【问题描述】

在这里插入图片描述

【输入格式】

在这里插入图片描述

【输出格式】

在这里插入图片描述

【样例1】

【样例输入1】

3 4 5

【样例输出1】

.#..
##..
....

【样例说明1】

在这里插入图片描述

【样例2】

【样例输入2】

10 10 10

【样例输出2】

##........
##........
..........
..........
..........
..........
..........
..........
..........
#........#

【样例说明2】

如果在边界，朝着边界外移动一格，直接跳转到另一头

【解题思路】

老汉使用到的是状压的解题方式

将移动方向状态压缩为1、2、3、4，进行标识，根据题目需求进行操作

代码注释有详细过程

【代码】

package ABC339_B_LangtonsTakahashi;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int h = scan.nextInt();int w = scan.nextInt();int n = scan.nextInt();// 创捷网格char[][] hw = new char[h][w];// 网格初始化为全白for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {hw[i][j] = '.';}}// 记录桥位置，初值为(1,1)，在数组中为(0,0)int i = 0;int j = 0;// 方向标记上、右、下、左分别对应1、2、3、4，初始为向上// 1// 4 2// 3int dir = 1;// 共进行n次操作while (n-- > 0) {// 当当前点为白色时if (hw[i][j] == '.') {// 改成黑色hw[i][j] = '#';// 顺时针旋转为+1dir++;// 根据方向移动(i,j)坐标if (dir % 4 == 1) {if (i > 0) {i--;} else {i = h - 1;}} else if (dir % 4 == 2) {if (j < w - 1) {j++;} else {j = 0;}} else if (dir % 4 == 3) {if (i < h - 1) {i++;} else {i = 0;}} else {if (j > 0) {j--;} else {j = w - 1;}}}// 当当前点为黑色时else if (hw[i][j] == '#') {// 改成白色hw[i][j] = '.';// 逆时针旋转为-1dir--;if (dir % 4 == 1) {if (i > 0) {i--;} else {i = h - 1;}} else if (dir % 4 == 2) {if (j < w - 1) {j++;} else {j = 0;}} else if (dir % 4 == 3) {if (i < h - 1) {i++;} else {i = 0;}} else {if (j > 0) {j--;} else {j = w - 1;}}}}// 输出最终结果for (int i1 = 0; i1 < h; i1++) {for (int j1 = 0; j1 < w; j1++) {System.out.print(hw[i1][j1]);}System.out.println();}scan.close();}
}