[TIOJ 1230] 尋寶問題

作法：

給的網格很小，而且要求的是兩條起點到終點的亂走的路徑，大概只能DFS暴搜( 插頭DP不知道有沒有辦法作，沒學過OAO 不過就算可以的話應該也比這作法麻煩 )，所以很開心的寫了暴搜傳上去，就有一筆測資TLE了。TLE的測資也不難想像，只要 n,m 取最大然後完全沒有障礙物就夠他跑了。

所以必須要加一些剪枝，因為這個問題類似之前在作書上習題(算法競賽入門經典 第二版)作到的UVa 11882，所以剪枝方法也類似。第一個方法就是如果現在是第二個人在走，而且他走到這步之後會讓之後沒辦法再走到終點了(也就是和終點不連通)，則剪枝。所以會在每次DFS到一個點的時候另外做一次DFS。但這樣還不夠，那筆測資一樣會TLE。下一個方法則是如果把和當前格子連通的所有寶物都吃到了，還會比當前最佳解差，則也剪枝。用這兩個方法就能過這題了。

UVa那題的剪枝方法也類似，就是考慮當前格子所在的連通塊，如果全部數字都能吃到，而且假設有辦法排成一個最大的數字，這樣也比最佳解差則剪枝。

code :

#include<bits/stdc++.h>
using namespace std;
 
int dx[]={1,-1,0,0},dy[]={0,0,1,-1} ;
int n,m ;
int G[10][10],ans,num=0 ;
bool vis[2][7][7],vis2[2][7][7] ;
 
int num2 ;
void dfs2(int x,int y,int t)
{
    vis2[t][x][y]=1 ; num2+=G[x][y] ;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i] , ny=y+dy[i] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(G[nx][ny]==-1 || vis[t][nx][ny]) continue ;
        if(vis2[t][nx][ny]) continue ;
        dfs2(nx,ny,t) ;
    }
}
 
bool check(int x,int y,int t)
{
    memset(vis2[t],0,sizeof(vis2[t])) ;
    num2=0 ;
    dfs2(x,y,t) ;
    return vis2[t][n-1][m-1] && (t==0 || num2+num > ans) ;
}
 
void dfs(int x,int y,int t)
{
    if(!check(x,y,t)) return ;
    if(t==1 && x==n-1 && y==m-1) { ans=max(ans,num) ; return ; }
    if(x==n-1 && y==m-1) { dfs(0,0,1) ; return ; }
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i] , ny=y+dy[i] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(G[nx][ny]==-1 || vis[t][nx][ny]) continue ;
        int tmp=G[nx][ny] ;
        G[nx][ny]=0 ; vis[t][nx][ny]=1 ; num+=tmp ;
        dfs(nx,ny,t) ;
        G[nx][ny]=tmp ; vis[t][nx][ny]=0 ; num-=tmp ;
    }
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
    {
        char s[5] ; scanf("%s",s) ;
        if(s[0]=='x') G[i][j]=-1 ;
        else G[i][j]=s[0]-'0' ;
    }
    ans=0 ;
    vis[0][0][0]=1 ;
    num=G[0][0] ; G[0][0]=0 ;
    dfs(0,0,0) ;
    printf("%d\n",ans) ;
}