给你一个棋盘,最大是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 " ,ans); } return 0; }