正方形划分【dfs】

3

5 8
2 4
3 3
3 4
3 5
4 2
4 4
4 5
5 5

3 2
1 1
3 3

2 4
1 1
1 2
2 1
2 2

YES
NO
YES

解题思路：从左上角开始遍历，如果存在一个石子，则向下遍历，并标记以扫描的区域，如果没找到则递归回退，直到跳出

#include <cstdio>
#include <cstring>

int L, N, a[22][22], vis[22][22], xx, yy;

int js(int x, int y, int len) {//记石子个数
    int cnt = 0;
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            if (a[x+i][y+j]) cnt++;
    return cnt;
}

void mark(int x, int y, int len, int k) {//标记
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            vis[x+i][y+j] = k;
}

void getNext(){ //获取下一个顶点
     for (int i = 1; i <= L; i++)
        for (int j = 1; j <= L; j++)
            if (vis[i][j] == false) {
                xx = i; yy = j;
                return;
            }
}

int my_find(int x, int y, int n){
    int len, cnt;
    for(len = 1; x + len <= L + 1 && y + len <= L + 1; len++){
        cnt = js(x, y, len);
        if(cnt == 0) continue;
        else if(cnt > 1) return 0;
        mark(x, y, len, 1);
        n -= len * len;
        if(!n) return 1;
        getNext();
        if (my_find(xx, yy, n))
            return 1;
        else { // 递归恢复现场
            mark(x, y, len, 0);
            n += len * len;
        }
    }
    return 0;
}

int main(){
    int T, r, c;
    scanf("%d",&T);
    while(T--){
        memset(a, 0, sizeof(a));
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &L, &N);
        for(int i = 1; i <= N; i++){
            scanf("%d%d",&r,&c);
            a[r][c] = 1;
        }
        if( my_find(1, 1, L * L) )  printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

正方形划分【dfs】

原文：http://blog.csdn.net/hpuhjl/article/details/44899595