F . Biggest Number

题意:

找出最大的字符串,不能一个地方走两次,不能走墙

思路:

看到数据量直接劝退,但是换种思路;其实这个题就是剪枝使得不超时,DFS是很好想到,重点就是剪枝.怎么剪枝那?

首先我们这样看.我们要找出最大的数,那么没有零越长这个数肯定就越长,所以第一步就是保证最长.

之后当两个或几个都一样长的话,就要从头比较大小,选大的,淘汰小的.

所以我们粗略的找到这两个特点就用与剪枝

1. 保证最长,只需要看他连通块中还有没有选择,没有选择,就只能这样的.所以我们看他当前的可选的长度与前面统计的答案长度长短,如果比他短好,直接不用在看了,他一定没办法比我们原来的答案大. 这就是一个剪枝.

2. 其次我们看同长度,比大小,当我们发现当前连通块长度,与答案长度相同,那就比较已经记录的连通块长度,看到哪个大,如果原答案大,那也不用往后看了,直接退出即可.

通过这两个剪枝能剪掉很多,不必要的深搜.

const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

ll r,c;
string ans;
ll vis[30][30],dis[30][30];
string str[30];

ll getLen(ll x,ll y){
    if(dis[x][y] == 1) return 0;
    dis[x][y] = 1;
    ll sum=1;
    for(int i=1;i<=4;i++){
        ll fx=x+dx[i];
        ll fy=y+dy[i];
        if(fx<0 || fx>=r || fy<0 || fy>=c||dis[fx][fy] ||str[fx][fy]=='#') continue;
        sum+=getLen(fx,fy);
    }
    return sum;
}

string maxS(string a,string b){
    if(a.size()==b.size()){
        return max(a,b);
    }else {
        if(a.size()>b.size()) return a;
        else return b;
    }
}
void dfs(ll x,ll y,string s){
    if(vis[x][y] == 1) return;
    s = s + str[x][y];

    memcpy(dis,vis,sizeof vis);
    ll len = getLen(x,y)-1;//去掉当前这个长度

    if(len+s.size() <ans.size()) return ;//长度不够

    if (len+s.size() == ans.size()) {//长度相同，但不可能比答案更大 
        if(s<ans.substr(0,(ll)s.size())) return ;
    }

    if(len==0) { ///没可以选的字符 更新答案
        ans=maxS(ans,s);
        return ;
    }

    vis[x][y]=1;
    for(int i=1;i<=4;i++){
        ll fx=dx[i]+x;
        ll fy=dy[i]+y;
         if(fx<0 || fx>=r || fy<0 || fy>=c|| vis[fx][fy] ||str[fx][fy]=='#') continue;
         else dfs(fx,fy,s);
    }
    vis[x][y]=0;
}
int main()
{
    while(cin>>r>>c){
        if(r==c&&r==0) return 0;
        for(int i=0;i<r;i++){
            cin>>str[i];
        }
        ans="";
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(str[i][j]!='#'){
                    memset(vis,0,sizeof vis);
                    dfs(i,j,"");
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}