首页 > 代码库 > (BFS)aoj0558-Cheese
(BFS)aoj0558-Cheese
题目地址
根据题意,必须按从1吃到n的顺序。建立vi数组记录去没去过某一点,从起点向四周搜索,合法且未去过就入队列。每当找到符合此时应吃的位置,就将这个位置改为‘.‘并刷新vi数组,清空队列(因为必须要这时从这点出发才能用时最短)再从这一点继续这个过程,直到遇到n位置且体力为n结束,输出步数。
参考代码:
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include <iostream> 5 using namespace std; 6 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}},sj[1005][1005]; 7 char maze[1005][1005]; 8 bool vi[1005][1005]; 9 typedef pair<int ,int >P; 10 int h,w,n,ti=1; 11 int bfs(int oi,int oj) 12 { 13 queue<P> que; 14 que.push(P(oi,oj));P p; 15 while(que.size()) 16 { 17 p=que.front(); 18 que.pop(); 19 if(maze[p.first][p.second]-‘0‘==n&&ti==n) 20 return sj[p.first][p.second]; 21 if(maze[p.first][p.second]-‘0‘==ti) 22 { 23 memset(vi,false,sizeof(vi)); 24 vi[p.first][p.second]=true; 25 while(que.size()) 26 { 27 que.pop(); 28 } 29 30 maze[p.first][p.second]=‘.‘; 31 ti++; 32 } 33 for(int i=0;i<4;i++) 34 { 35 int xx,yy; 36 xx=p.first+dir[i][0]; 37 yy=p.second+dir[i][1]; 38 if(xx>=0&&xx<h&&yy>=0&&yy<w&&maze[xx][yy]!=‘X‘&&vi[xx][yy]==false) 39 { 40 vi[xx][yy]=true; 41 sj[xx][yy]=sj[p.first][p.second]+1; 42 que.push(P(xx,yy)); 43 } 44 } 45 } 46 } 47 int main() 48 { 49 memset(sj,0,sizeof(sj)); 50 memset(vi,false,sizeof(vi)); 51 scanf("%d%d%d",&h,&w,&n); 52 int i,j,an; 53 for(i=0;i<h;i++) 54 { 55 scanf("%s",maze[i]); 56 } 57 for(i=0;i<h;i++) 58 { 59 for(j=0;j<w;j++) 60 { 61 if(maze[i][j]==‘S‘) 62 { 63 vi[i][j]=true; 64 an=bfs(i,j); 65 printf("%d\n",an);return 0; 66 } 67 } 68 } 69 }
(BFS)aoj0558-Cheese
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。