図論の検索部分の解題の構想

2164 ワード

HU 1728:http://acm.hdu.edu.cn/showproblem.php?pid=1728
この問題は難しくないです。簡単なBFSです。その複雑なところは一番小さい回転数を見つけることです。
#include<iostream>
#include<queue>
using namespace std;
int Sx,Sy,Ex,Ey,T;
int visit[101][101];
int n,m;
char Map[101][101];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node
{
	int x;
	int y;
	int step; //    
	int dir;

}; 
void BFS(int x,int y)
{
  queue<Node> Q;
  Node New;
  New.x=x;
  New.y=y;
  New.step=0;
  New.dir=-1;  //         
  visit[x][y]=0;  //   
  Q.push(New);
  while(!Q.empty())
  {
	  New=Q.front(); 
	  Q.pop();	  
	  int u;
	  for(u=0;u<4;u++)
	  {
		  Node top=New;
		  top.x+=dir[u][0];
		  top.y+=dir[u][1];
		  if(top.x<1||top.x>n||top.y<1||top.y>m||Map[top.x][top.y]=='*') //  、   
		  continue;
			  if(top.dir!=u&&top.dir!=-1) //    ,   
				  top.step++; 
			  if(top.step>T) //    ,    ,    
				  continue;
			  if(top.x==Ex&&top.y==Ey) //  
			  {
				  cout<<"yes"<<endl;
				  return;
			  }
			  if(visit[top.x][top.y]>=top.step) //      ,    
			  { 
				  top.dir=u;
			  visit[top.x][top.y]=top.step;
			  Q.push(top);
			  }
	
	  }
  }
  cout<<"no"<<endl;
  return;
}
int main()
{
	int N;
	while(cin>>N)
	{	
		while(N--)
		{
			cin>>n>>m;
			memset(Map,0,sizeof(Map));
			int i,j;
			for(i=1;i<=n;i++)			
				for(j=1;j<=m;j++)				
				{
					cin>>Map[i][j];
					visit[i][j]=999;  //            
				}
			cin>>T>>Sy>>Sx>>Ey>>Ex;  //    
			if(Sx==Ex&&Sy==Ey)
			{
				cout<<"yes"<<endl;
				continue;
			}
			BFS(Sx,Sy); //      
		}
	}
	return 0;
}