hdu1175 题目链接；http://acm.hdu.edu.cn/showproblem.php?pid=1175； 题目大意；就是转弯只能转两次；只能走0的地方；首末位置的数字要相同；这题还要注意减枝容易超时 hdu1728 题目链接；http://acm.hdu.edu.cn/showproblem.php?pid=1728； 题目大意；给定转弯次数；问在要求内是否可以达到目的地；注意首末地址的输入方式；可以先进行处理； NBUT；1642； 题目链接；https://ac.2333.moe/Problem/view.xhtml?id=1642； 题目大意；只看第二种情况； 要求每次都必须转弯；也就是说每个节点到下个节点的方向要不是相同的；这个有点点难理解； 题目源代码最后面摆出来; 分析；；；；；；
题型分类 暂时把bfs法转弯问题分为两类； 1；列如1175和1728的那种，限制了转弯的次数求最优解； 2；列如1642；第二次bfs时每次都必须转弯先看第一种；这个一样的可以套模板；转弯次数一定，那么我们就每次每个点方向搜索的时候把一个方向全部搜索完；搜索到尽头； 然后在出队列；后面照旧；如果达到了转弯次数还没有搜到就不能按要求搜到了；；； 可以自己模拟一下；看这部分代码实现；
这是1175的那部分代码；还要注意减枝一下 while(!q.empty()) { now=q.front(); q.pop(); if(now.x==x2&&now.y==y2&&now.w<=2) { return 1; } if(now.w>2)//减枝；； { //q.pop(); continue; } for(i = 0; i < 4; i++) { a=now.x+dir[i][0]; b=now.y+dir[i][1]; while(a>=1&&a<=n&&b>=1&&b<=m&&mp[a][b]==0)//一条方向走到底；；这里也是while； { if(mark[a][b]==0) { next.x=a;next.y=b;next.w=now.w+1; mark[a][b]=1; q.push(next); } a+=dir[i][0];//在while内部；；；； b+=dir[i][1]; } } }方向问题的第一种就这样解决了；基本上可以套用这样的模板；
要在k次转弯内问是否可以达到要求； 可以每次搜索方向的时候一条方向搜完；这样可以很好的解决这个问题； **要特别注意；**最先初始化方向次数，一般是为-1；这样才能保证；从起点开始的4个方向的节点都是0转弯；**** 先全部是不用转弯的；全部搜索一遍；达到要求的入队列； 然后在在0转弯并且达到要求的点的前提下再搜索； 每次都这样；看是否可以在k次之内在要求之内达到目的地；第一种类型的说完了；看第二种类型的吧； 每次都要转弯；我看到这个知识点的时候就有两个东西一直搞混了； 我把方向搜索过程中的不同向和节点路径的转弯搞混淆了； 其实节点路径的转弯就跟我们普通的bfs那个标记路径是否重复类似的只是这里变成三维数组；标记方向是否重复；三维数组的第三维表示这个节点的这个方向是否走过；mark1[now.x][now.y][i]==0；就是看next.x，next.y的i方向是否走过；走过那么就会标记成1了； 而搜索方向就是；now.bj!=i；就是问上一节点的方向bj是否还是i如果是那么我们则不能再走这个方向了； 注意这两个方向都是；上个节点对要走的节点的方向；因此都是now，而不是next；这个要注意； 可以看代码了；对着代码理解吧；特别看那个if判断的方向判断；；；
就是1642的部分代码 now.x=r1;now.y=l1;now.num=mp[r1][l1];now.bj=-1; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); for(i = 0; i < 4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mp[next.x][next.y]!=-1&&now.bj!=i&&mark1[now.x][now.y][i]==0) { next.bj = i; mark1[now.x][now.y][i]=1; next.num=now.num+mp[next.x][next.y]; if(next.x==r2&&next.y==l2) { printf("%d\n",next.num); return 1; } q.push(next); } } }暂时关于转弯的bfs就到这了；
/* “连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则： 在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子）， 而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看， 咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就 只能将错就错了，连线不能从外围绕过。 玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。 Input 输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)， 分别表示棋盘的行数与列数。在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。 0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50)，表示下面有q次询问。 在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。 n=0,m=0时，输入结束。 注意：询问之间无先后关系，都是针对当前状态的！ */ #include<stdio.h> #include<stdlib.h> #include<iostream> #include<queue> #include<algorithm> #include<stack> #include<set> #include<string.h> using namespace std; //依据是转弯问题的bfs；套路依旧；一个方向走到底；不过这个题目容易超时所以要剪纸加限定条件 //超时了几次，wa了几次； //没有减枝，没有考虑是同一点的情况；bfs时终点没有先处理一下；；； int mp[1005][1005]; int mark[1005][1005]; int n, m,x1,x2,y11,y2; struct node { int x, y,w; }; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int bfs() { mp[x2][y2]=0;//处理终点；；因为下面要搜到终点，因此要处理一下；；； int i, a,b; memset(mark,0,sizeof(mark)); queue<node> q; node now,next; now.x=x1;now.y=y11;now.w=-1;//依据处理为-1； mark[x1][y11]=1; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(now.x==x2&&now.y==y2&&now.w<=2) { return 1; } if(now.w>2)//减枝；； { //q.pop(); continue; } for(i = 0; i < 4; i++) { a=now.x+dir[i][0]; b=now.y+dir[i][1]; while(a>=1&&a<=n&&b>=1&&b<=m&&mp[a][b]==0)//一条方向走到底；； { if(mark[a][b]==0) { next.x=a;next.y=b;next.w=now.w+1; mark[a][b]=1; q.push(next); } a+=dir[i][0]; b+=dir[i][1]; } } } return 0; } int main() { int i, j, tt,p; while(~scanf("%d %d",&n, &m)) { if(n==0&&m==0) break; for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) scanf("%d",&mp[i][j]); } scanf("%d",&tt); while(tt--) { scanf("%d %d %d %d",&x1,&y11,&x2,&y2); //mp[x2][y2]=0; if((mp[x1][y11]!=mp[x2][y2])||(mp[x1][y11]==0))//减支处理；；； { printf("NO\n"); } else if(x1==x2&&y11==y2) printf("NO\n"); else { p = bfs(); mp[x2][y2]=mp[x1][y11]; if(p==1) { printf("YES\n"); } else printf("NO\n"); } } } 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; //hdu1728;bfs限制条件为转弯次数限制不大于k；因此bfs搜索时要有个方向走到底；意思就是说队列不是相邻距离存放的而是一个方向的存放； //还有就是要注意输入；输入字符串的时候要注意；（下面以注释） //注意他参数的输入；先列再行；所以要记得处理一下； //对于队列压入的问题；将这个元素((结构体)压入队列；则这个元素原有的值也不存在了；；；(这个bug搞了好久；） int s1,s2,e1,e2,k,n,m; char mp[105][105]; int mark[105][105]; struct node { int x, y,w; }; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; void bfs() { int i; queue<node> q; memset(mark,0,sizeof(mark)); node now,next; now.x=s1;now.y=s2;now.w=-1; mark[now.x][now.y] = 1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==e1&&now.y==e2&&now.w<=k) { printf("yes\n"); return ; } for(i = 0; i < 4; i++) { int a=now.x+dir[i][0]; int b=now.y+dir[i][1]; while(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]=='.') { if(mark[a][b]==0) { next.x=a;next.y=b; next.w = now.w+1;//这个要放里面；意思就是每次压入队列后next原有的值也没有了； //printf("%d %d\n",a,b); mark[a][b]=1; q.push(next); } a=a+dir[i][0]; b=b+dir[i][1]; } } } printf("no\n"); return ; } int main() { int tt,i,j; scanf("%d",&tt); while(tt--) { scanf("%d %d",&n, &m); for(i = 0; i < n; i++) { scanf("%s",mp[i]);//尽量别用i=1还用%s输入；这种情况j还是从0开始 } // for(i = 0; i < n; i++) // { // for(j = 0; j < m; j++) // printf("%c",mp[i][j]); // printf("\n"); // } scanf("%d %d %d %d %d",&k,&s2,&s1,&e2,&e1); s2--;s1--;e1--;e2--; bfs(); } return 0; } #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #include<iostream> #include <bits/stl_queue.h> using namespace std; int mp[505][505]; int n, m, r1,r2,l1,l2; struct node { int x, y, num,bj; friend bool operator<(node a, node b) {return a.num>b.num;} }; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int mark1[505][505][4]; bool bfs()//第二种；；； { int i; priority_queue<node> q; node now,next; memset(mark1,0,sizeof(mark1)); now.x=r1;now.y=l1;now.num=mp[r1][l1];now.bj=-1; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); for(i = 0; i < 4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mp[next.x][next.y]!=-1&&now.bj!=i&&mark1[now.x][now.y][i]==0) { next.bj = i; mark1[now.x][now.y][i]=1; next.num=now.num+mp[next.x][next.y]; if(next.x==r2&&next.y==l2) { printf("%d\n",next.num); return 1; } q.push(next); } } } return 0; } bool bfs2() { int i; priority_queue<node> q; node now,next; int mark[505][505]={0}; now.x=r1;now.y=l1;now.num=mp[r1][l1]; mark[r1][l1]=1; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); for(i = 0; i < 4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mp[next.x][next.y]!=-1&&mark[next.x][next.y]!=1) { mark[next.x][next.y]=1; next.num=now.num+mp[next.x][next.y]; if(next.x==r2&&next.y==l2) { printf("%d ",next.num); return 1; } q.push(next); } } } return 0; } int main() { int num,i, j, l,len,kk=1; char ch[5000]; while(~scanf("%d %d %d %d %d %d",&n,&m,&r1,&l1,&r2,&l2)) { r1=r1-1;r2=r2-1; l1=l1-1;l2=l2-1; getchar(); for(i = 0; i < n;i++) { l=0; gets(ch); len = strlen(ch); for(j = 0; j < len; j++) { if(ch[j]=='*') { mp[i][l]=-1; l++; } else if(ch[j]>='0'&&ch[j]<='9') { num = ch[j]-'0'; if(ch[j+1]>='0'&&ch[j+1]<='9') { num = num*10+(ch[j+1]-'0'); j++; if(ch[j+1]>='0'&&ch[j+1]<='9') { num = num*10+(ch[j+1]-'0'); j++; } } mp[i][l]=num; l++; } } } printf("Case %d: ",kk++); if(bfs2()==0) { printf("-1 "); } int aa=bfs(); if(aa==0) { printf("-1\n"); } //printf("iwdffuf\n"); } return 0 ; }