注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 3368  

2012-07-17 21:54:12|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=3368

DFS

题意:给出了一个棋盘的状态,现在放一颗黑棋,问最多能把多少颗白旗翻转了,翻转的规则是:这颗黑棋和另一颗黑棋连线之间都是白旗,则这些白旗都能被翻转

注意:可以多个方向的翻转白旗

解法:遍历一遍,如果是'*',则进行搜索,即假设该位上放一黑棋

/*
 * fudq.cpp
 *
 *  Created on: 2012-07-17
 *      Author: fudq
 */
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
char f[10][10];
int dir[8][2] = {{0, 1}, {0, -1},{1, 0},{-1, 0},{1, 1},{-1, -1},{1, -1},{-1, 1}};
int sum,res;

void DFS(int x,int y,int d,int num)
{
 int i;
 if(x<0 || x>7 || y<0 || y>7)
  return ;
 if(d==8)//如果是最初的状态,则进行8个方向的搜索
 {
  for(i=0;i<8;i++)
   DFS(x+dir[i][0],y+dir[i][1],i,num);
 }
 else
 {
  if(f[x][y]=='*')//如果是空白位置,则返回,不符合条件
   return ;
  else if(f[x][y]=='D')//如果是黑棋,则说明连线之间都是白旗,应该把白旗数做和相加,并结束本次搜索
  {
   sum+=num;
   return ;
  }
  else
   DFS(x+dir[d][0],y+dir[d][1],d,num+1);//如果是白旗,则继续按着这个方向进行搜索
 }
}

void make()
{
 int i,j;
 res=0;
 for(i=0;i<8;i++)
  for(j=0;j<8;j++)
  {
   sum=0;
   if(f[i][j]=='*')//如果是空位,则表示能在这放黑棋,进行搜索
    DFS(i,j,8,0);
   if(sum>res)
    res=sum;
  }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int T,i,cas;
    scanf("%d",&T);
    cas=1;
    while(T--)
    {
     for(i=0;i<8;i++)
     {
      scanf("%s",f[i]);
      getchar();
     }
     make();
     printf("Case %d: %d\n",cas++,res);
    }
 return 0;
}

  评论这张
 
阅读(100)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018