図論の検索部分の解題の構想
2164 ワード
HU 1728:http://acm.hdu.edu.cn/showproblem.php?pid=1728
この問題は難しくないです。簡単なBFSです。その複雑なところは一番小さい回転数を見つけることです。
この問題は難しくないです。簡単な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;
}