求一个剪枝方案
我的代码
思路:暴搜+蒟佬能想到的所有剪枝
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<string>
#include<iomanip>
#include<algorithm>
using namespace std;
int m,n,a[111][111];
bool vis[111][111];
int maxn=9999;
int f[8]={-1,0,0,-1,0,1,1,0};
void dfs(int i,int j,int sum,int ys)
{
if(i>m||j>m||i<=0||j<=0) return;
if(i==m&&j==m)
{
if(sum<maxn)
maxn=sum;
return;
}
if(sum>=maxn) return;//仅有的剪枝
for(int t=0;t<7;t+=2)
{
int x=i+f[t];
int y=j+f[t+1];
if(x>m||y>m||x<=0||y<=0) continue;
if(vis[x][y]==true) continue;
if(a[x][y]==0){
if(a[i][j]!=0)
{
vis[x][y]=true;
dfs(x,y,sum+2,a[i][j]);
vis[x][y]=false;
}
}
else if(a[x][y]!=ys)
{
vis[x][y]=true;
dfs(x,y,sum+1,a[x][y]);
vis[x][y]=false;
}
else if(a[x][y]==ys)
{
vis[x][y]=true;
dfs(x,y,sum,a[x][y]);
vis[x][y]=false;
}
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
a[x][y]=c+1;
}
vis[1][1]=true;
dfs(1,1,0,a[1][1]);
if(maxn!=9999) printf("%d",maxn);
else cout<<-1;
return 0;
}