hdu1175 连连看

#include<iostream>

#include<queue>

using namespace std;

int n,m;

int map[1005][1005];

typedef struct s_e

{

int x,y,f,c;

};

s_e start,end;

int d[4][2]={​{1,0},{0,1},{-1,0},{0,-1}};

int visited[1005][1005];

int BFS(s_e s)

{

queue <s_e>q;

q.push(s); visited[s.x][s.y]=0;

while(!q.empty())

{

s_e temp; temp=q.front();

q.pop();

// if(temp.c>2) continue;

if(temp.x==end.x&&temp.y==end.y&&temp.c<=2) return 1;

for(int i=0;i<4;i++)

{

s_e now ;

now.x=temp.x+d[i][0];

now.y=temp.y+d[i][1];

now.f=i;

now.c=temp.c;

if(now.x>=0&&now.x<n&&now.y>=0&&now.y<m&&(now.x==end.x&&now.y==end.y||map[now.x][now.y]==0))

{

if(now.f!=temp.f)

{

now.c=temp.c+1;

if(now.c>2) continue;

if(visited[now.x][now.y]>=now.c)

{

visited[now.x][now.y]=now.c;

q.push(now);

}

}

else

{

if(visited[now.x][now.y]>=now.c)

{

visited[now.x][now.y]=now.c;

q.push(now);

}

}

}

}

}

return 0;

}

int main()

{

int i,j,k;

while(scanf("%d%d",&n,&m)!=EOF&&(m||n))

{

for(i=0;i<n;i++)

for(j=0;j<m;j++)

{

scanf("%d",&map[i][j]);

visited[i][j]=4;

}

scanf("%d",&k);

while(k--)

{

for(i=0;i<n;i++)

for(j=0;j<m;j++) visited[i][j]=4;

start.c=-1; start.f=-1;

scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);

start.x-=1;start.y-=1;end.x-=1;end.y-=1;

if(map[start.x][start.y]!=map[end.x][end.y]) {cout<<"NO"<<endl; continue; }

if(map[start.x][start.y]==0) { cout<<"NO"<<endl; continue; }

if(BFS(start))

{

cout<<"YES"<<endl;

continue;

}

cout<<"NO"<<endl;

}

}

return 0;

}

http://acm.hdu.edu.cn/showproblem.php?pid=1175

题意：找到两个相同的数字 拐弯个数不能超过2 还有一些限制条件在这里就不在赘述了

思路： 开始我用DFS 结果超时 下次想问题时一定要确定用什么方法去解决问题 总体方针没有正确后面再好也会错

       用BFS找 过程中要注意用visited[][]标记每个点的拐弯数 如果遍历到它时 本身拐弯数小于等于该点的 则可以遍历该

       点；其他方法都比较基本不在赘述