首页 > 代码库 > Poj2157Maze 搜索
Poj2157Maze 搜索
用一个5进制数来位压钥匙的状态,然后 判重就好了。 这题写戳了,反正是问能不能到,直接bfs 搜,打开一扇门在把它加入队列继续搜,看最后能不能搜到结果。
#include<stdio.h>#include<iostream>#include<algorithm>#include<string.h>#include<math.h>using namespace std;int dx[] = {-1,1,0,0};int dy[] = {0,0,-1,1};int cifang(int a,int b){ int ans =1 ; for(int i =0;i<b;i++) ans*= a; return ans;}int flag;int ex,ey;char str[100][100];int n,m;int val[10];int vis[20][20][4000];void dfs(int x,int y,int sum){ if(vis[x][y][sum]) return ; // printf("%d %d %d\n",x,y,sum);system("pause"); if(flag) return ; if(x==ex&&y==ey){ flag = 1;return ; } vis[x][y][sum]=1; for(int i = 0;i<4;i++){ int xx = dx[i]+ x;int yy= dy[i] +y; if(flag) return ; if(xx>=0&&xx<n&&yy>=0&&yy<m&&str[xx][yy]!=‘X‘){ if(str[xx][yy]>=‘A‘&&str[xx][yy]<=‘E‘){ int t =str[xx][yy] - ‘A‘; int gg = sum % cifang(5,t+1) / cifang(5,t); if(gg==val[t]){ dfs(xx,yy,sum); } } else if(str[xx][yy]>=‘a‘&&str[xx][yy]<=‘e‘){ int t=str[xx][yy]-‘a‘; int gg = sum+cifang(5,t); char t1 = str[xx][yy]; str[xx][yy]=‘.‘; dfs(xx,yy,gg); str[xx][yy] = t1; } else dfs(xx,yy,sum); } }}int main(){ int sx,sy; while(cin>>n>>m,n||m){ flag = 0; memset(vis,0,sizeof(vis)); memset(val,0,sizeof(val)); for(int i =0 ;i<n;i++){ scanf("%s",str[i]); for(int j = 0;j<m;j++){ if(str[i][j]>=‘a‘&&str[i][j]<=‘e‘){ val[str[i][j]-‘a‘]++; } if(str[i][j]==‘S‘){ sx = i;sy = j; } if(str[i][j] == ‘G‘){ ex = i ;ey = j; } } } dfs(sx,sy,0); if(flag){ printf("YES\n"); } else printf("NO\n"); } return 0;}
Poj2157Maze 搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。