1429: 蓝桥杯2014年第五届真题-兰顿蚂蚁（BFS版）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int n,m,k,sx,sy;
int a[1001][1001];
int fy[6]={0,0,1,0,-1};
int fx[6]={0,1,0,-1,0};
struct Node
{
	int x;
	int y;
	int zt;
};
char ss;
int endstep;
queue<Node> q;
int tx,ty;

void bfs()
{
	
	Node startnode;
	startnode.x=sx;
	startnode.y=sy;
	startnode.steps=1;
	q.push(startnode);
	while(true)
	{
     	Node newnode;
     	
    	if(q.front().steps-1==endstep){ return;}
    	
    	if(a[q.front().x][q.front().y]==0)
	    {
	    	
	    	if(k==4) 
			{ 
		    	k=1;newnode.x=q.front().x+fx[k];
		    	newnode.y=q.front().y+fy[k];
			}
			else{
				//cout<<'Y';
				k++;newnode.x=q.front().x+fx[k];
				newnode.y=q.front().y+fy[k];
			}
		    newnode.steps=q.front().steps+1;
			a[q.front().x][q.front().y]=1;
		//	cout<<"白格"<<newnode.x<<' '<<newnode.y<<endl;
		    
	    }
	    else if(a[q.front().x][q.front().y]==1)
		{
		    
		    if(k==1) 
		    {
				k=4;newnode.x=q.front().x+fx[k];
				newnode.y=q.front().y+fy[k];
				
			}
			else {
				k--;newnode.x=q.front().x+fx[k];
				newnode.y=q.front().y+fy[k];
				
			}
			newnode.steps=q.front().steps+1;
		        a[q.front().x][q.front().y]=0;
		  //  cout<<"黑格"<<newnode.x<<' '<<newnode.y<<endl;
	    }
	   // cout<<newnode.x<<' '<<newnode.y<<endl;
		q.push(newnode);
     	q.pop();
   	}
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
		for(int j=0;j<m;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>sx>>sy>>ss>>endstep;
	if(ss=='L') k=4;
	else if(ss=='R') k=2;
	else if(ss=='U') k=3;
	else if(ss=='D') k=1;
	bfs();
	cout<<q.back().x<<' '<<q.back().y<<endl;
	return 0;
}