本文主要是介绍hdu 1226 BFS + bfs记录路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1226
为了省空间，可以用vis数组初始化的时候初始化为-1，
发现一个BFS容易错的地方 开始一直WA在这里：就是我int tp=q.front();之后马上q.pop()；了，然后才去判断是不是符合条件以break，这样就不能根据q.empty()==1认为没有找到ans 因为这里WA了
其实也可以vis[0] == -1来判断
比较不理解的是 当n==0的时候 %n==0的时候怎么处理
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000;const int MAXN = 5000+100;
int n,c,m;
int a[MAXN],vis[MAXN],pre[MAXN];//pre记录路径
int ans[MAXN];queue<int>q;int num;void dfs(int u)
{ans[num++]=vis[u];if(pre[u] == -1)return;dfs(pre[u]);
}void print()
{num--;while(!ans[num])num--;for(int i=num;i>=0;i--)printf("%c",ans[i]+ (ans[i]>9?'A'-10:'0') );putchar('\n');
}void solve()
{CL(vis,0xff);CL(pre,0xff);if(!n && !a[0]){puts("0");return;}if(!n && a[0])//{puts("give me the bomb please");return;}while(!q.empty())q.pop();for(int i=0;i<m;i++)if(a[i]){int tmp=a[i]%n;if(vis[tmp]==-1){vis[tmp]=a[i];//记录tmp由a[i]得来pre[tmp]=-1; //q.push(tmp);}}int tp=0,flag=0;while(!q.empty()){tp=q.front();q.pop();if(!tp){flag=1;break;}for(int i=0;i<m;i++){int tmp=(tp*c+a[i])%n;if(vis[tmp] == -1){vis[tmp]=a[i];pre[tmp]=tp;q.push(tmp);}}}if(!flag){puts("give me the bomb please");return;}num=0;dfs(0);if(num>500){puts("give me the bomb please");return;}print();
}int main()
{//IN("hdu1226.txt");int ncase;scanf("%d",&ncase);while(ncase--){scanf("%d%d%d",&n,&c,&m);char op[5];for(int i=0;i<m;i++){scanf("%s",op);if(op[0] >='A' && op[0] <='F') a[i]=op[0]-'A'+10;else a[i]=op[0]-'0';}sort(a,a+m);solve();}return 0;
}
这篇关于hdu 1226 BFS + bfs记录路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
