首页 > 代码库 > 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 搜索