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
",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
");
        }
        else printf("NO
");
    }
    return 0;
}