本文共 7078 字，大约阅读时间需要 23 分钟。
HDU 1175 连连看
//BFS#include #include using namespace std;bool flag;int n,m,q,x1,y1,x2,y2;int map[1005][1005];int visit[1005][1005];int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0}}; // 上下左右方向struct node{ int x, y; int dir[2]; // 用于保存上次走的方向 int count; // 已转弯的次数}s,t;queue Q;void BFS(){ int i,j,temp=map[x2][y2]; // 所点的两个数字不同、两次点同一个、点到了元素为0(没有棋子)的情况直接输出NO if((map[x1][y1]!=map[x2][y2]) || (x1==x2 && y1==y2) || (!map[x1][y1] || !map[x2][y2])){ printf("NO\n"); return; } // 如果点在外面的情况则不能，输出NO if(x1<0 || x1>=n || y1<0 || y1>=m || x2<0 || x2>=n || y2<0 || y2>=m){ printf("NO\n"); return; } // 初始化访问标记 memset(visit,false,sizeof(visit)); visit[x1][y1] = true; while(!Q.empty()) Q.pop(); s.x = x1, s.y=y1, s.dir[0]=s.dir[1]=0, s.count=0; Q.push(s); while(!Q.empty()){ t=Q.front(); Q.pop(); for(i=0; i<4; ++i){ s = t; // 剪枝，如果转弯次数已经是2，目标不能不同行又不同列，且下一步的方向必须与上一次相同而不能转弯 if(s.count==2 && (s.x!=x2 && s.y!=y2 || (s.dir[0]!=dir[i][0] || s.dir[1]!=dir[i][1])) ) continue; s.x+=dir[i][0]; s.y+=dir[i][1]; if((s.dir[0]!=dir[i][0] || s.dir[1]!=dir[i][1]) && s.dir[0]!=s.dir[1]) ++s.count; s.dir[0] = dir[i][0], s.dir[1] = dir[i][1]; if(s.count>2) continue; if(s.x==x2 && s.y==y2){// 是否符合条件的 if(s.count<=2){ printf("YES\n"); return; } continue; } //是否压入队列 if(s.x>=0 && s.x =0 && s.y
HDU 1072 Nightmare
// BFS#include #include #include #include using namespace std;int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1}};int T,N,M,x1,y1,x2,y2;int map[10][10], visit[10][10]; // visit存经过那个位置时所剩下的时间struct node{ int x,y; int count; // 走过的步数 int time; // 用过的时间}s,t;queue Q;bool is_out(int x,int y,int time){ if(x==x2 && y==y2 && time<6) return true; return false;}void BFS(){ memset(visit,6,sizeof(visit)); // 初始化为6, 如果用过的时间为6的话那么就不能再走了 visit[x1][y1] = 0; while(!Q.empty()) Q.pop(); s.x=x1, s.y=y1, s.count=0, s.time=0; Q.push(s); while(!Q.empty()){ t = Q.front(); Q.pop(); if(is_out(t.x,t.y,t.time)){ printf("%d\n",t.count); return; } for(int i=0; i<4; ++i){ int dx = t.x+dir[i][0]; int dy = t.y+dir[i][1]; int dt = t.time+1; // dt =0 && dx =0 && dy
HDU 1241 Oil Deposits
/*BFS题目，依次枚举，当遇到一个是'@'的，就通过广搜，把所有搜到的都做上标记*/#include #include using namespace std;int m,n,num,cnt;char map[105][105];// 八个方向，刚开始就是因为忽略还有斜对角线，导致一直不能过，浪费了很多时间int dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}};struct node{ int x,y;}s,t;queue Q;void BFS(){ if(!num){ printf("0\n"); return; } cnt=0; for(int i=0; i =0 && dx =0 && dy
HDU 1241 rescue
#include #include #include #include using namespace std;int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1}};int map[205][205];char a[205][205];int N,M,x1,y1,x2,y2;bool flag;struct node{ friend bool operator < (node a,node b){ return a.step > b.step; //优先步数少的 } int x,y,step;}n,m;int main(){// freopen("input.txt","r",stdin); int i,j; while(scanf("%d %d",&N,&M)!=EOF){ for(i=0; i Q; //建立优先队列 Q.push(n); while(!Q.empty()){ m = Q.top(); Q.pop(); if(m.x==x2 && m.y==y2){ //达到目标退出循环 flag=true; break; } for(i=0; i<4; ++i){ n.x = m.x+dir[i][0]; n.y = m.y+dir[i][1]; if(n.x>=0 && n.x =0 && n.y = map[n.x][n.y]) continue; map[n.x][n.y] = n.step; Q.push(n); } } } if(flag) printf("%d\n",m.step); else printf("Poor ANGEL has to stay in the prison all his life.\n"); } return 0;}
HDU 1253 胜利大逃亡
#include #include #include #include using namespace std;int K,A,B,C,T,x1,y1,z1;int map[52][52][52];bool visit[52][52][52];int dir[6][3]={ {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};struct node{ int x,y,z; int count;}s,temp;queue Q;bool is_next(int x,int y,int z){ if(x>=0 && x =0 && y=0 && z T){ printf("-1\n"); return; } while(!Q.empty()) Q.pop(); // 确保队列为空 memset(visit,false,sizeof(visit)); // 初始化访问标记 visit[0][0][0] = true; //所关地方标志为以走过 s.x=0,s.y=0,s.z=0,s.count=0; Q.push(s); while(!Q.empty()){ temp = Q.front(); Q.pop(); if(temp.x==A-1 && temp.y==B-1 && temp.z==C-1 && temp.count<=T){ printf("%d\n",temp.count); return; } if(temp.count>T) break; for(int i=0; i<6; ++i){ int x = temp.x+dir[i][0]; int y = temp.y+dir[i][1]; int z = temp.z+dir[i][2]; if(is_next(x,y,z)){ s.x = x, s.y=y, s.z=z, s.count=temp.count+1; visit[x][y][z] = true; Q.push(s); } } } printf("-1\n");}int main(){ // freopen("input.txt","r",stdin); int i,j,k; scanf("%d",&K); while(K--){ scanf("%d %d %d %d",&A,&B,&C,&T); for(i=0; i
HDU 1312 Red and Black
#include #include #include using namespace std;int h,w,cnt,x1,y1;char map[25][25];bool visit[25][25];int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1}};struct node{ int x,y;}s,q;queue qq;void BFS(){ cnt = 1; memset(visit,false,sizeof(visit)); while(!qq.empty()) qq.pop(); visit[x1][y1] = true; s.x = x1, s.y = y1; qq.push(s); while(!qq.empty()){ q = qq.front(); qq.pop(); for(int i=0; i<4; ++i){ int dx = q.x+dir[i][0]; int dy = q.y+dir[i][1]; if(dx>=0 && dx =0 && dy
HDU 1026 Ignatius and the Princess I
#include #include using namespace std;int N,M;int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1}};char map[105][105];bool visit[105][105];struct node{ friend bool operator < (const node a, const node b){ return a.cost>b.cost; } int x,y; int cost;}a,b;struct pathnode{ int prex, prey;}path[105][105];// 倒着搜回去void BFS(){ memset(visit,false,sizeof(visit)); visit[N-1][M-1] = true; path[N-1][M-1].prex = -1; // 终点标记 a.x=N-1, a.y=M-1, a.cost=0; //注意出口可能会有怪兽 if(map[N-1][M-1] != '.') a.cost = map[N-1][M-1]-'0'; priority_queue Q; Q.push(a); while(!Q.empty()){ b=Q.top(); Q.pop(); for(int i=0; i<4; ++i){ a = b; a.x += dir[i][0]; a.y += dir[i][1]; // 超出范围的、'X'不能走的、走过的，直接跳过 if(a.x<0 || a.x>=N || a.y<0 || a.y>=M || map[a.x][a.y]=='X' || visit[a.x][a.y]) continue; visit[a.x][a.y] = true; // 处理这一格花了多少时间 if(map[a.x][a.y] == '.') ++a.cost; else a.cost += map[a.x][a.y]-'0'+1; path[a.x][a.y].prex = b.x; path[a.x][a.y].prey = b.y; if(a.x==0 && a.y==0){ printf("It takes %d seconds to reach the target position, let me show you the way.\n",a.cost); int x=a.x, y=a.y, key=1; while(path[x][y].prex != -1){ int tx=path[x][y].prex; int ty=path[x][y].prey; printf("%ds:(%d,%d)->(%d,%d)\n",key++,x,y,tx,ty); if(map[tx][ty]!='.'){ for(int j=0; j
转载地址：http://gkzni.baihongyu.com/