本文主要是介绍hdu 1104 Remainder(BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1104
题目大意：
n,k,m
n可以 +-*% m，最后求的 n mod k==（初始n+1）mod k
%与mod区别：
%的得数可以有正有负，其正负取决于被除数
mod的得数只能为正
1.
需要处理下%后的正负问题.
不难理解：n mod k==（n%k+k）%k
2.
因为需要mod k 所以最后的答案一定在0~（k-1）之间，需要建立一个数组记录该数是否被遍历过，这样便有了范围。
3.
因为有%m的操作，所以不能直接%k，而使用%（k与m的公倍数，比如k*m）。
剩下就是一般的BFS了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<utility>
using namespace std;typedef pair<string,int>si;//first路径second此时n的值
const int MAXN=1e3+10;
bool vis[MAXN];
int n,m,k,km,ans;void BFS()
{memset(vis,0,sizeof(vis));queue<si>q;si s;s.first="";s.second=n;q.push(s);while(!q.empty()){si ts=q.front();q.pop();if((ts.second%k+k)%k==ans){cout<<ts.first.length()<<endl;cout<<ts.first<<endl;return;}string ss=ts.first;//临时变量int nown=ts.second;for(int i=0;i<4;i++){switch(i){case 0:ts.second=(nown+m)%km;ts.first=ss+'+';break;case 1:ts.second=(nown-m)%km;ts.first=ss+'-';break;case 2:ts.second=(nown*m)%km;ts.first=ss+'*';break;case 3:ts.second=(nown%m+m)%m%km;//为什么去掉多余的%km，运行时间反而更长了ts.first=ss+'%';break;}if(!vis[(ts.second%k+k)%k]){q.push(ts);vis[(ts.second%k+k)%k]=true;}}}cout<<0<<endl;
}int main()
{while(scanf("%d%d%d",&n,&k,&m)!=EOF&&(n||k||m)){km=k*m;ans=((n+1)%k+k)%k;//n+1 mod kBFS();}return 0;
}
这篇关于hdu 1104 Remainder(BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
