hdu4499 搜索

题意:
      给你一个棋盘,最大是5*5的,问你最多可以放多少个炮,炮和炮之间不可以相互攻击,这块只的是只能走一步,不存在两个炮中间三个棋子的情况..

思路:

   刚开始想的是把所有的空位置都放上炮,然后最大点权独立集,结果没有办法把这个图弄成二分图,没招了,直接搜索吧,把每一个点分成两种情况,如果之前就有棋子,那么无话说直接下进入下一层,如果没有棋子,我们有两种选择,放炮和不放炮,先把不放炮写上,然后判断下是否可以放,我的想法是当前的位置只会影响当前位置的这一行和这一列,直接判断吧当前位置放上炮后的这行和这列是否满足条件,判断方法是枚举任意三个连续(不一定相邻)的数组,看第一个和第二个是否都是炮,至于怎么枚举画下就知道了,其实可以优化的,我们是从左往右,从上往下的,所以可以直接判断上和左就行了,自己懒得优化了,5*5不大怎么写都行..

#include<stdio.h>
#include<string.h>

int num[6][6];
int mark[6][6];
int xx ,yy ,ans;


bool OK(int xxx ,int yyy)
{
int mk = 0;
int s ,s1 ,s2 ,s3;
for(int iii = 0 ;iii < 3 ;iii ++)
{
s = 0;
for(int ii = iii ;ii < yy ;ii ++)
{
if(!num[xxx][ii]) continue;
s++;
if(s == 1) s1 = num[xxx][ii];
if(s == 2) s2 = num[xxx][ii];
if(s == 3) s3 = num[xxx][ii];
if(s == 3) break;
}
if(s == 3 && s1== 2 && s3 == 2)
{
mk = 1;
break;
}
}
if(!mk)
for(int iii = 0 ;iii < 3 ;iii ++)
{
s = 0;
for(int ii = iii ;ii < xx ;ii ++)
{
if(!num[ii][yyy]) continue;
s++;
if(s == 1) s1 = num[ii][yyy];
if(s == 2) s2 = num[ii][yyy];
if(s == 3) s3 = num[ii][yyy];
if(s == 3) break;
}

if(s == 3 && s1== 2 && s3 == 2)
{
mk = 1;
break;
}
}
return mk == 0;
}

void DFS(int sum ,int nowx ,int nowy)
{
if(ans < sum) ans = sum;
int x = nowx ,y = nowy + 1;
if(y == yy)
{
x++ ,y = 0;
}
if(mark[x][y] || x == xx) return;
if(num[x][y])
{
mark[x][y] = 1;
DFS(sum ,x ,y);
mark[x][y] = 0;
}
else
{
mark[x][y] = 1;
DFS(sum ,x ,y);
mark[x][y] = 0;
num[x][y] = 2;
if(OK(x ,y))
{
mark[x][y] = 1;
DFS(sum + 1 ,x ,y);
mark[x][y] = 0;
}
num[x][y] = 0;
}
return ;
}


int main ()
{
int i ,q;
int x ,y;
while(~scanf("%d %d %d" ,&xx ,&yy ,&q))
{
memset(num ,0 ,sizeof(num));
for(i = 1 ;i <= q ;i ++)
{
scanf("%d %d" ,&x ,&y);
num[x][y] = 1;
}
ans = 0;
memset(mark ,0 ,sizeof(mark));
DFS(0 ,0 ,-1);
printf("%d\n" ,ans);

}
return 0;
}