蓝桥杯2014年第五届真题-兰顿蚂蚁 dfs解法

解题思路:
还是按照dfs的模板来，只需要控制好蚂蚁的方向就可以，而且还不用回溯.
注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int m,n;
int  a[110][110];
char b[110][110];
int x,y,k;
char s; 
char t[]={'U','L','D','R'};  //蚂蚁的四个方向
char u[]={-1,0,1,0};    
char v[]={0,-1,0,1};
void dfs(int x,int y,int step){
	if(step==k){
		cout<<x<<" "<<y;
		return ;
	}
	if(a[x][y]==1){
		if(x>=0&&x<m&&y>=0&&y<n){
			for(int i=0;i<=3;i++){
				if(b[x][y]==t[i]){
					int nx=x+u[(i-1+4)%4];//蚂蚁方向改变
					int ny=y+v[(i-1+4)%4];
					b[nx][ny]=t[(i-1+4)%4];
					a[x][y]=0;
					dfs(nx,ny,step+1);
					break;
				}
			}
		}
	}else{
		if(x>=0&&x<m&&y>=0&&y<n){
			for(int i=0;i<=3;i++){
				if(b[x][y]==t[i]){
					int nx=x+u[(i+1)%4]; //蚂蚁方向改变
					int ny=y+v[(i+1)%4];
					b[nx][ny]=t[(i+1)%4];
					a[x][y]=1;
					dfs(nx,ny,step+1);
					break;
				}
			}
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	cin>>x>>y>>s>>k;
	b[x][y]=s;
	dfs(x,y,0);
	return 0;
}