LETTERS（字母）

poj 1154

题目描述：给出一些字母组成一个地图，要求若下一步能行得通，必须是没有走过的字母，即路径中不能出现相同的字母

解决：DFS+回溯

/*本来是加了个vis数组，想着将走过的每一步
进行标记，其实不需要vis，
因为有26个字母的b数组控制着呢，
若走过了肯定不会再走重复了
，但是最多也相当于用了vis和没用一样啊，
为什么用了vis反而wa了呢*/
#include <iostream>
#include <bitset>
using namespace std;
int m,n,maximal=0;
char map[25][25];
bitset<26> b;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int x,int y,int current_step)
{

    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx >= 0  && nx <m && ny >=0 && ny <n )
        {
            if(b[map[nx][ny]-'A'] == 1 ){ 
             if(current_step > maximal)maximal=current_step;
            }
            else
            {
                b[map[nx][ny]-'A']=1;
                dfs(nx,ny,current_step+1);
                b[map[nx][ny]-'A']=0;
           }
        }
    }
}

int main()
{
    cin>>m>>n;
    for(int i = 0; i < m; i++)cin>>map[i];
    b.reset();
    b[map[0][0]-'A']=1;
    dfs(0,0,1);
    cout<<maximal<<endl;
    system("pause");
    return 0;
}