题解 | #[NOIP2017]棋盘#

我来贡献一篇dfs加剪枝优化ac的代码吧，应该是比较好理解的一种， 主要优化： 1.用d数组记录到达i，j时的最小花费，每次搜索前判断花费是否小于d，否则不搜。 2.用st布尔类型数组记录i，j是否走过，走过的不搜。

using namespace std;
int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
bool st[120][120];
int m,n,mp[120][120],x,y,c,ans = 999999,d[120][120];
void dfs(int px,int py,int cnt,int mo) 
{
	//剪枝
	if(cnt >= ans) return;
    //更新答案
    if(px==m&&py==m) 
	{
        ans = min(ans,cnt);
        return;
    }
    //四个方向
    for(int i = 0; i < 4; i++) 
    {
        int nx = px + dx[i],ny = py + dy[i];
        //不越界
        if(nx>=1&&nx<=m&&ny>=1&&ny<=m&&!st[nx][ny]) 
        {
            //上一层没有用魔法
            if(mo==3) 
            {
            //同颜色
            if(mp[nx][ny]==mp[px][py]) {
            	st[nx][ny] = true;
            	d[nx][ny] = min(d[nx][ny],cnt);
            	dfs(nx,ny,cnt,3);
            	st[nx][ny] = false;
			}
            //不同颜色
            if(mp[nx][ny]!=mp[px][py]&&mp[nx][ny]!=3)
            {
            	if(cnt+1<d[nx][ny])
            	{
            		st[nx][ny] = true;
            	    d[nx][ny] = min(d[nx][ny],cnt+1);
            	    dfs(nx,ny,cnt+1,3);
            	    st[nx][ny] = false;
				}
            
			}
            //空白颜色
            if(mp[nx][ny]==3)
            {
            	if(cnt+2<d[nx][ny])
            	{
            		st[nx][ny] = true;
            		d[nx][ny] = min(d[nx][ny],cnt+2);
            	    dfs(nx,ny,cnt+2,mp[px][py]);
            	    st[nx][ny] = false;
				}
			}
                
            }
            //使用了魔法
            else
            {
            //同颜色
            if(mp[nx][ny]==mo)
            {
            	st[nx][ny] = true;
            	d[nx][ny] = min(d[nx][ny],cnt);
            	dfs(nx,ny,cnt,3);
            	st[nx][ny] = false;
			}
            //不同颜色
            if(mp[nx][ny]!=mo&&mp[nx][ny]!=3)
            {
            	if(cnt+1<d[nx][ny])
            	{
            		st[nx][ny] = true;
            	d[nx][ny] = min(d[nx][ny],cnt+1);
            	dfs(nx,ny,cnt+1,3);
            	st[nx][ny] = false;
				}
            	
			}
            }
        }
        
    }
    
}
int main() {
    cin>>m>>n;
    //初始化
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= m; j++)
        {
        	mp[i][j] = 3;
        	d[i][j] = 9999;
		}
            
    }
    //赋值
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d",&x,&y,&c);
        mp[x][y] = c;
    }
    dfs(1,1,0,3);
    if(ans == 999999) cout<<-1;
    else  cout<<ans;
  
}