hdu3368 dfs 下棋

两颗黑子之间的白子可以翻装成黑子，两颗白子之间的黑子可以翻转成白子，对于一个给定位置，有八个方向有翻转其他颜色的子的可能。规则之一是下棋的位置一定要能翻转对方的子。

求最优情况：黑子能翻转的白子个数的最大值。只要对有限的位置进行搜索就行，搜索8*8的位置，每个位置搜索八个方向，每个方向分别计算白子数量，直到遇到黑子，计算八个方向翻转

的白子的和，更新最大值。

下面两种代码稍有不同，当设置图的坐标为[1,8]*[1,8]时，边界可以不用管，当坐标是[0,7]*[0,7]时需要检查是否越界。

 /*171ms 1376k*/

 #include<iostream>

 #include<cstdio>

 #include<string.h>

 using namespace std;

 char map[][];

 int kase,t;

 int sum;

 int MAX;

 int dir[][]{{,},{-,},{,},{,-},{,},{,-},{-,},{-,-}};

 int dfs(int x,int y)

 {

     sum=;

     int xx,yy;

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

     {

        int num=;//每个搜索方向开始时翻转白子的数量都置零

         xx=x+dir[i][];

         yy=y+dir[i][];

        while(map[xx][yy]=='L')

        {

            num++;

            xx+=dir[i][];

         yy+=dir[i][];

        }

        if(map[xx][yy]=='D')sum+=num;//八个方向翻转的白子总和

     }

     return sum;

 }

 int main()

 {

        scanf("%d",&t);

        for(kase=;kase<=t;kase++)

        {

            int MAX=;

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

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

               {

               scanf(" %c",&map[i][j]);}//要根据全局地图来判断max,所以先保存map，不能边存边计算

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

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

               {

               if(map[i][j]=='*')

               {

                   MAX=max(MAX,dfs(i,j));

               }

            }

             printf("Case %d: %d\n",kase,MAX);

        }

 }

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a) memset(a,0,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define pb(i) push_back(i)

 #define ppb(x) pop_back(x)

 #define maxn 8

 int n,m,t;

 int Map[maxn][maxn];

 int dir[][]={{,},{,-},{,},{-,},{,},{,-},{-,},{-,-}};

 int dfs(int x,int y)

 {

     int cnt=;

     int xx,yy;

     f(i,,)

     {

         int tot=;

         int  xx=x+dir[i][];

         int  yy=y+dir[i][];

         if(xx>=||xx<||yy<||yy>=)continue;

         while((xx+dir[i][])<=&&(xx+dir[i][])>=&&(yy+dir[i][])<=&&(yy+dir[i][])>=&&Map[xx][yy]=='L')

         {

             tot++;

             xx+=dir[i][];

             yy+=dir[i][];

         }

         if(Map[xx][yy]=='D')cnt+=tot;

     }

     return cnt;

 }

 int ans;

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

     scan(n);

     f(tt,,n)

     {

         ans=;

         f(i,,)

             f(j,,)

             {

                 scanf(" %c",&Map[i][j]);

             }

         f(i,,)

             f(j,,)

             {

                 if(Map[i][j]=='*')

                 ans=max(ans,dfs(i,j));

             }

         pf("Case %d: %d\n",tt,ans);

     }

  }