hdu1548； 题目链接；http://acm.hdu.edu.cn/showproblem.php?pid=1548； 题目大意；电梯问题；只有两个方向；上下； hdu1372 题目链接；http://acm.hdu.edu.cn/showproblem.php?pid=1372； 题目大意；象棋里面马走向的问题；方向就是马走日的方位；
例如1548； 电梯；每层楼都有一个值；这个值就是在这层楼可以通过电梯上这么多层或者下这么多层；问从a层是否可以到达b层； 套用模板就是把for循环改成两个if而已；
mark[now.x] = 1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==b)//判断放前面；防止a==b的情况； { return now.step; } next.x=now.x-mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } next.x=now.x+mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } } return -1;列如；1372； 就是简单的套模板就是把方向改变一下；在纸上模拟一下马日的走向；；；
int dir[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};代码；
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<queue> #include<algorithm> #include<stack> #include<set> #include<string.h> using namespace std; //两种移动方式； //之前把没有考虑a==b的情况一直wa； int n, a, b,bs; int mp[205]; int mark[205]; struct node { int x,step; }; int bfs() { queue<node> q; node now,next; memset(mark,0,sizeof(mark)); now.x = a;now.step=0; mark[now.x] = 1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==b)//判断放前面；防止a==b的情况； { return now.step; } next.x=now.x-mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } next.x=now.x+mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } } return -1; } int main() { int i; while(~scanf("%d",&n)&&n!=0) { scanf("%d %d",&a,&b); for(i = 1; i <= n; i++) { scanf("%d",&mp[i]); } printf("%d\n",bfs()); } return 0; }第二道
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<queue> #include<algorithm> #include<stack> #include<set> #include<string.h> using namespace std; //只是8个方向不同而已；没有限制条件； int s1,s2,e1,e2,bs; struct node { int x,y,t; }; int mark[10][10]; int dir[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}}; void bfs() { int i; queue<node>q; memset(mark,0,sizeof(mark)); node now, next; now.x=s1;now.y=s2;now.t=0; mark[now.x][now.y]=1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==e1&&now.y==e2) { bs = now.t; return ; } for(i = 0; i < 8; i++) { next.x = now.x+dir[i][0]; next.y = now.y+dir[i][1]; if(next.x>=1&&next.x<=8&&next.y>=1&&next.y<=8&&mark[next.x][next.y]==0) { mark[next.x][next.y] = 1; next.t = now.t+1; q.push(next); } } } return ; } int main() { char a1 ,b1; int a2,b2; while(~scanf("%c%d %c%d",&a1,&a2,&b1,&b2)) { getchar(); s1 = a1-96;s2=a2; e1 = b1-96;e2=b2; bfs(); printf("To get from %c%d to %c%d takes %d knight moves.\n",a1,a2,b1,b2,bs); } return 0; }