HDU 1045(炮台安置 DFS)

题意是在 n*n 的方格中进行炮台的安置，炮台不能处于同一行或同一列（类似于八皇后问题），但若是炮台间有墙壁阻挡，则可以同时安置这对炮台。问图中可以安放的最大炮台数目。

用深搜的方法，若此处为空地，则分四个方向继续向下，若直到搜到墙壁或图外也没有搜到已放置的炮台，则可以在当前位置添加炮台，继续向下，反之则不能添加炮台，求出最大的炮台数即可。

 #include <bits/stdc++.h>

 using namespace std;

 int dir[][] = {,,,,-,,,-};//{0,1,0,-1,1,0,-1,0};

 int n,flag,ans,newx,newy,mp[][];

 char s[];

 void dfs(int sum)

 {

     if(sum > ans) ans = sum;

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

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

         {

             if(mp[i][j] == )

             {

                 flag = ;

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

                 {

                     newx = i;

                     newy = j;

                     while()

                     {

                         newx += dir[k][];

                         newy += dir[k][];

                         if(mp[newx][newy] == ||mp[newx][newy] == -) break;

                         else if(mp[newx][newy] == )

                         {

                             flag = ;

                             break;

                         }

                     }

                 }   if(flag)

                     {

                         mp[i][j] = ;

                         dfs(sum+);

                         mp[i][j] = ;

                     }

             }

         }

 }

 int main()

 {

     while(~scanf("%d",&n)&&n)

     {

         memset(mp,-,sizeof(mp));

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

         {

             scanf("%s",s+);

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

             {

                 if(s[j] == '.') mp[i][j] = ;

                 else mp[i][j] = ;

             }

         }

         ans = ;

         dfs();

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

HDU 1045(炮台安置 DFS)

最新文章

热门文章