P9700题解

思路

看数据范围，发现范围很小，直接用搜索。

搜索时枚举每个点，如果有棋子就枚举方向，如果这个方向合法，则将剩余棋子数减一，继续搜索。

搜索时参数只需要传当前棋子数就行了。

有以下几点需要注意

• 多组数据每次需要初始化。

• 判断是否合法时要注意。

• 每次记得回溯棋子。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,m,k,dx1[4]={-2,0,2,0},dy1[4]={0,-2,0,2},dx2[4]={-1,0,1,0},dy2[4]={0,-1,0,1};
int minn=1e9;
bool a[10][10];
void dfs(int cnt){
	for(int x=1;x<=n;x++){
		for(int y=1;y<=m;y++){
			if(!a[x][y])continue;
			for(int i=0;i<4;i++){
				int nx=x+dx1[i];
				int ny=y+dy1[i];
				if(nx<1||nx>n||ny<1||ny>m||!a[x+dx2[i]][y+dy2[i]]||a[nx][ny]){
					continue;
				}
				a[x+dx2[i]][y+dy2[i]]=0;
				a[x][y]=0;
				a[nx][ny]=1;
				dfs(cnt-1);
				a[x+dx2[i]][y+dy2[i]]=1;
				a[x][y]=1;
				a[nx][ny]=0;
			}
		}
	}
	minn=min(minn,cnt);

}
int main(){
	int T;
	cin>>T;
	while(T--){
		memset(a,0,sizeof a);
		cin>>n>>m>>k;minn=k;
		for(int i=1;i<=k;i++){
			int x,y;
			cin>>x>>y;
			a[x][y]=1;
		}
		dfs(k);
		cout<<minn<<endl;
	}
    return 0;
}