正方形划分【dfs】

简介: Problem Description 一个边长为L的正方形可以分成 L*L个小正方形. 有N个石子放在 N个小正方形里,能否将它分成 N个 正方形,使得每个正方形里恰有一个石子且这N 个正方形恰好构成整个正方形 .

Problem Description
一个边长为L的正方形可以分成 L*L个小正方形. 有N个石子放在 N个小正方形里,能否将它分成 N个 正方形,使得每个正方形里恰有一个石子且这N 个正方形恰好构成整个正方形 .
 

Input
输入数据首先包含一个整数T,表示测试实例的个数,然后是T组数据,每组第一行包含2个整数L,N,接下来有N行每行2个整数 r,c,表示第r行c列的小正方形里有一个石子 .1<L<=20;1<N<=L*L; 1<=r,c<=L.
 

Output
对于每个测试实例,如能将它分成 N个 正方形输出YES, 否则输出 NO
 

Sample Input
 
 
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
 

Sample Output
 
 
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;
}


目录
相关文章
|
6月前
|
人工智能 移动开发 算法
【动态规划】【C++算法】LeetCoce996正方形数组的数目
【动态规划】【C++算法】LeetCoce996正方形数组的数目
|
3月前
|
算法 C++
空间或平面判断两线段相交(求交点)
空间或平面判断两线段相交(求交点)
19 0
|
6月前
6366. 在网格图中访问一个格子的最少时间(dijkstra在矩阵上的运用)
6366. 在网格图中访问一个格子的最少时间(dijkstra在矩阵上的运用)
|
6月前
|
算法 前端开发
前端算法-岛屿的最大面积-DFS(深度优先搜索)
前端算法-岛屿的最大面积-DFS(深度优先搜索)
28 0
|
6月前
|
算法 前端开发
前端算法 岛屿的最大面积 DFS(深度优先搜索)
前端算法 岛屿的最大面积 DFS(深度优先搜索)
31 0
|
6月前
|
算法 测试技术 C#
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
|
6月前
leetcode-1725:可以形成最大正方形的矩形数目
leetcode-1725:可以形成最大正方形的矩形数目
35 0
|
6月前
|
算法 程序员 索引
【算法训练-动态规划 四】【二维DP问题】最大正方形、最小路径和、不同路径
【算法训练-动态规划 四】【二维DP问题】最大正方形、最小路径和、不同路径
99 0
|
算法
巧解“求取矩形面积划分”
巧解“求取矩形面积划分”
103 0
|
定位技术
DFS:迷宫解的方案数
DFS:迷宫解的方案数