题意 给你一个数n，你要找出一个只由0和1组成的不超过100位的数，使得该数是n的m倍 思路 这是一道BFS题，入队的时候有两种情况：一种是10t；一种是10t+1；这题还有个坑点是用C++的STL的队列会T,所以需要自己写一个队列 题目链接 http://poj.org/problem?id=1426 代码 #include<iostream>#include<queue>using namespace std; long long a[10000000]; long long bfs(int N) { int front = 0; int rear = 0; a[rear++] = 1; while (front != rear) { long long tmp = a[front++]; if (tmp % N == 0) { return tmp; } a[rear++] = tmp * 10; a[rear++] = tmp * 10 + 1; } return -1; } int main() { int N; while (cin >> N) { if (N == 0)break; cout << bfs(N) << endl; } return 0; } ……

阅读全文

什么是BFS BFS又称为广度优先搜索。举个例子：一群老鼠走迷宫。假设老鼠是无限多的，这群老鼠进去后，在每个路口派出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有其他老鼠探索过了，也停下。很显然，所有的道路都会走到，而且不会重复。这个思路就是BFS。BFS看起来像“并行计算”，不过，由于程序是单机顺序运行的，所以可以把BFS看成是并行计算的模拟。 如何实现BFS 在具体编程时，一般用队列这种数据结构来具体实现BFS，甚至可以说“BFS=队列”。 代码如下： #include<iostream>#include<queue>#define CHECK(x,y)(x>=0&&x<=wx&&y>=0&&y<=hy) using namespace std; int wx,hy,num; char room[23][23]; int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; struct node{ int x,y; } void BFS(int dx,int dy){ num=1; queue<node>q; node start,next; start.x=dx; start.y=dy; q.push(start); while(!q.empty()){ next=q.front(); q.pop(); for(int i=0;i<4;i++){ next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; if(CHECK(next.y,next.y)&&room[next.x][next.y]=='.'){ room[next.x][next.y]='#'; num++; q.push(next); } } } } int main(){ int dx,dy,x,y; while(cin>>wx>>hy){ if(wx==0&&hy==0)break; for(y=0;y<hy;y++){ for(x=0;x<wx;x++){ cin>>room[x][y]; if(room[x][y]=='@'){ dx=x; dy=y; } } } num=0; BFS(dx,dy); cout<<num<<endl; } return 0; } ……

阅读全文