基础算法题——德邦国王（dfs、剪枝）

太过爱你忘了你带给我的痛 2022-11-21 03:40 113阅读 0赞

### [德邦国王][Link 1] ###

![题目1][1]  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
![题目3][3]

--------------------

题目还算中规中矩，就是剪枝比较麻烦。  
**解题思路：dfs**  
剪枝：  
①、移动次数不超过设定值 M。  
②、若有解，则后面的步骤不可大于该解的值。  
③、不断查询完美矩阵与当前矩阵不同的个数 t 。  
t - 1 为最快可将当前矩阵移动成完美矩阵的步数，若 t - 1 + 已经移动的步数 cnt 大于 最优解时，则该情况不必再往下移动。

--------------------

AC代码

#include<bits/stdc++.h>
    using namespace std;
    int now[10][10], per[10][10];
    int n, k, m, ans=20;
    struct node{ 
    	int dx, dy;
    }p[10];
    
    //判断 x 矩阵是否是 per 矩阵 
    bool judge1(int jz[10][10], int cnt){ 
    	int t=0;
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=n; j++){ 
    		if(jz[i][j]!=per[i][j]){ 
    			t++;
    		}
    	} 
    	if(t>ans-cnt+1||t>m-cnt+1) return true;
    	if(t==0) ans = min(cnt, ans);
    	return false;
    }
    
    void dfs(int jz[10][10], int cnt, int x, int y, int z){ 
    	if(cnt>m||cnt>=ans||judge1(jz, cnt)) 
    		return;
    	
    	for(int i=0; i<k; i++){ 
    		if(i==z) continue;
    		int dx = p[i].dx;
    		int dy = p[i].dy;
    		if(x+dx<=n&&y+dy<=n&&x+dx>=1&&y+dy>=1){ 
    			jz[x][y]=jz[x+dx][y+dy];
    			jz[x+dx][y+dy]=2;
    			dfs(jz, cnt+1, x+dx, y+dy, i);
    			jz[x+dx][y+dy]=jz[x][y];
    			jz[x][y]=2;
    		}
    	}
    }
    
    int main(){ 
    	int x, y;
    // freopen("data.txt", "r", stdin);
    	cin>>n>>k>>m;
    	for(int i=0; i<k; i++)
    		cin>>p[i].dx>>p[i].dy;
    	
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=n; j++){ 
    		cin>>now[i][j];
    		if(now[i][j]==2) x=i,y=j;
    	}
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=n; j++)
    		cin>>per[i][j];
    	
    	dfs(now, 0, x, y, -1);
    	if(ans!=20)
    		cout<<ans<<endl;
    	else
    		cout<<"-1\n";
    		
    	return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/7872/H
[1]: /images/20221120/495483d2d3d04fd0a802cb6b7b56ffde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6689feda7bf5446ca0fcef0e6940e1e6.png
[3]: /images/20221120/3e581e8ed0cd4ad2b6ac4a01c55d2041.png