不喜欢状压只喜欢dfs的小萌新30分求助!!

P2704 [NOI2001] 炮兵阵地

忘无羡机 @ 2019-05-25 07:42:25

#include<bits/stdc++.h>
using namespace std;
int ans,n,m;
int a[105][15],vis[105][15];
int max(int x,int y){return x > y ? x : y;}
void dfs(int x,int y,int num){
    if(x == n && y == m + 1)
    {
        ans = max(ans,num);
        return;
    }
    if(a[x][y] && !vis[x][y])
    {
        vis[x][y] = 1;
        vis[x + 1][y] = 1;
        vis[x + 2][y] = 1;
        vis[x - 1][y] = 1;
        vis[x - 2][y] = 1;
        vis[x][y + 1] = 1;
        vis[x][y + 2] = 1;
        vis[x][y - 1] = 1;
        vis[x][y - 2] = 1;
        if(y == m && x < n)
            dfs(x + 1,1,num + 1);
        else 
            dfs(x,y + 1,num + 1);
        vis[x][y] = 0;
        vis[x + 1][y] = 0;
        vis[x + 2][y] = 0;
        vis[x - 1][y] = 0;
        vis[x - 2][y] = 0;
        vis[x][y + 1] = 0;
        vis[x][y + 2] = 0;
        vis[x][y - 1] = 0;
        vis[x][y - 2] = 0;
    }
    else 
    {
        if(y == m && x < n)
            dfs(x + 1,1,num);
        else 
            dfs(x,y + 1,num);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
        {
            char ch = getchar();
            while(ch != 'P' && ch != 'H')ch = getchar();
            if(ch == 'P')       a[i][j] = 1;
            if(ch == 'H')       a[i][j] = 0;
        }
    dfs(1,1,0);
    printf("%d\n",ans);
} 

by 忘无羡机 @ 2019-05-25 07:42:50

额不对,是40分...


by 忘无羡机 @ 2019-05-25 07:48:40

数据太大了实在不想去调试了...

请各位大佬原谅


by Agakiss @ 2019-05-25 08:38:02

位运算快,所以为什么状压模板题T了那当然用状压鸭我是萌新


by Social_Zhao @ 2019-05-25 09:07:16

搜索状态太复杂了吧......这种题用状压dp吧。

或者您把vis用位运算置位实现一下?

还有我对周四中午跟我一个机房的小学生在讨论区怼您的事深表抱歉。


by Social_Zhao @ 2019-05-25 09:07:25

@忘无羡机


by 忘无羡机 @ 2019-05-25 11:25:18

小萌新表示不记得发生了什么...

●﹏●@Social_Zhao


by Social_Zhao @ 2019-05-25 11:29:54

我也是服了这几个小学生了。图片可以点


by Social_Zhao @ 2019-05-25 11:29:59

@忘无羡机


by Social_Zhao @ 2019-05-25 11:30:31

???不行

这里


by 忘无羡机 @ 2019-05-25 11:32:23

我就是觉得你这个ID很陌生没见过...


|