洛谷 P3956 棋盘 题解

每日一题 day5 打卡

Analysis

深搜+剪枝+瞎jb判断

1.越界

2.这个点无色

3.当前的价值已经比答案大

三种情况要剪枝

我搜索里判断要不要施法的时候没判断上一次有没有施法，白调了0.5h，呵呵~~~

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define maxn 100+10

 #define INF 2147483647/2-1

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int m,n,ans=INF;

 int map[maxn][maxn],val[maxn][maxn];

 int d1[]={,,-,,},d2[]={,,,,-};

 inline void dfs(int nx,int ny,int ns,int flag)

 {

     if(nx<||nx>m||ny<||ny>m||map[nx][ny]==||ns>=val[nx][ny]) return;

     val[nx][ny]=ns;

     if(nx==m&&ny==m)

     {

         ans=min(ans,ns);

         return;

     }

     for(int i=;i<=;i++)

     {

         int xx=nx+d1[i],yy=ny+d2[i];

         if(map[xx][yy]>&&map[nx][ny]==map[xx][yy]) dfs(xx,yy,ns,);

         else if(map[xx][yy]>&&map[nx][ny]!=map[xx][yy]) dfs(xx,yy,ns+,);

         else if(map[xx][yy]==&&!flag)

         {

             map[xx][yy]=map[nx][ny];

             dfs(xx,yy,ns+,);

             map[xx][yy]=;

         }

     }

 }

 int main()

 {

     memset(val,,sizeof(val));

     m=read();n=read();

     for(int i=;i<=n;i++)

     {

         int x,y,z;

         x=read();y=read();z=read();

         map[x][y]=z+;

     }

     dfs(,,,false);

     if(ans==INF) write(-);

     else write(ans);

     return ;

 }

请各位大佬斧正