[蓝桥杯][2014年第五届真题]兰顿蚂蚁

题目

题目链接

题解

DFS。

没什么难的吧，可能实现的时候用时长短，代码简洁程度不同而已。

代码

#include
using namespace std;
const int N = 110;

int xx, yy, ax, ay, n, m, mp[N][N], stp;
char dir;

int dx[4] = {-1, 0, 1, 0}; // URDL   顺时针0~3 
int dy[4] = {0, 1, 0, -1};

void dfs(int sx, int sy, int d, int step) {
	if(step == stp) { ax=sx, ay=sy; return ; } // n步结束 
	
	d = (mp[sx][sy]?(d+1)%4:(4+d-1)%4);  // 黑格：顺时针转90，d+1对4取模为新的方向；白格：逆时针90，d-1对4取模为新方向，+4是防止出现负数 
	
	mp[sx][sy] ^= 1; // 格子颜色取反 
	
	dfs(sx+dx[d], sy+dy[d], d, step+1); // 新位置为 (sx+dx[d], sy+dy[d]) 
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i mp[i][j];
	cin>>xx>>yy>>dir>>stp;
	
	dfs(xx+1, yy+1, dir=='U'?0:dir=='R'?1:dir=='D'?2:3, 0);	// U：0 R：1 D：2 L：3  顺时针0~3 

	cout