本文主要是介绍POJ-2415 Hike on a Graph 搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接
题目大意：
在一个完全图（每条边都有各自的颜色）中有3个piece，每个piece只能沿一条边移动（移动的条件为：这条边的颜色与另外两个piece间的边的颜色一样）；问把三个piece移动到同一个点所需要的最小步数。
BFS里的结束判断还是找个一个判断好点 出队再判断数据大时间废挺大QAQ血的教训
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 55;
const int inf = 1<<30;
int n;
char map[maxn][maxn];
int vis[maxn][maxn][maxn];
struct node
{int a,b,c;node( int a,int b,int c):a(a),b(b),c(c){}node(){}
};
int BFS( node s )
{node cur;queue<node>que;memset(vis,0,sizeof(vis));vis[s.a][s.b][s.c] = 1;que.push(s);while( !que.empty() ){cur = que.front(); que.pop();if( cur.a == cur.b && cur.a == cur.c )return vis[cur.a][cur.b][cur.c] - 1;for( int i = 1; i <= n; i ++ ){if( map[cur.a][i] == map[cur.b][cur.c] && !vis[i][cur.b][cur.c] ){vis[i][cur.b][cur.c] = vis[cur.a][cur.b][cur.c] + 1;if( i == cur.b && i == cur.c )return vis[i][cur.b][cur.c] - 1;que.push(node(i,cur.b,cur.c));}if( map[cur.b][i] == map[cur.a][cur.c] && !vis[cur.a][i][cur.c] ){vis[cur.a][i][cur.c] = vis[cur.a][cur.b][cur.c] + 1;if( cur.a == i && cur.a == cur.c )return vis[cur.a][i][cur.c] - 1;que.push(node(cur.a,i,cur.c));}if( map[cur.c][i] == map[cur.a][cur.b] && !vis[cur.a][cur.b][i] ){vis[cur.a][cur.b][i] = vis[cur.a][cur.b][cur.c] + 1;if( cur.a == cur.b && cur.a == i )return vis[cur.a][cur.b][i] - 1;que.push(node(cur.a,cur.b,i));}}}return -1;
}
int main()
{//freopen("data.txt","r",stdin); node s;while( scanf("%d",&n) != EOF,n ){scanf("%d%d%d",&s.a,&s.b,&s.c);for( int i = 1; i <= n; i ++ ){for( int j = 1; j <= n; j ++ ){scanf(" %c",&map[i][j]);}}int ans = BFS(s);if( ans != -1 )printf("%d\n",ans);elseputs("impossible");}return 0;
}这篇关于POJ-2415 Hike on a Graph 搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
