黑马程序员技术交流社区

标题: DFS [打印本页]

---

作者: 善良的禽兽    时间: 2015-9-28 22:57
标题: DFS

#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 5
using namespace std;

int n, m, tot;
bool flag, state[N][N];

bool judge(int posy, int posx)
{
      if(state[posy][posx] || posy >= n || posx >= m)
               return false;
      return true;
}

void DFS(int cnt)
{
     if(flag && cnt == n * m)
     {
                tot++;
        return;
     }

     bool can = true;

     for(int i = 0; i < n && can; i++)
     {
        for(int j = 0; j < m && can; j++)
        {
             if(state[j])
                   continue;
             else
                               can = false;
   
             if(flag == false && judge(i, j + 1) && judge(i + 1, j) && judge(i + 1, j + 1))
             {
                                    flag = true;
                                    state[j] = state[i + 1][j] = state[j + 1] = state[i + 1][j + 1] = true;
                    DFS(cnt + 4);
                                    flag = false;
                                    state[j] = state[i + 1][j] = state[j + 1] = state[i + 1][j + 1] = false;
             }
             if(judge(i, j + 1))
             {
                                    state[j] = state[j + 1] = true;
                    DFS(cnt + 2);
                                    state[j] = state[j + 1] = false;
             }
             if(judge(i + 1, j))
             {
                                    state[j] = state[i + 1][j] = true;
                    DFS(cnt + 2);
                                  state[j] = state[i + 1][j] = false;
             }
                         state[j] = true;
             DFS(cnt + 1);
                         state[j] = false;
        }
     }
}

int main()
{
    int T;
    m = 4;
    scanf("%d", &T);
    while(T--)
    {
            tot = 0;
            flag = false;
        memset(state, false, sizeof(state));
        scanf("%d", &n);
        DFS(0);
        printf("%d\n", tot);
    }
    return 0;
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2