題目描述

?

題目分析?

本題使用遞歸模擬即可，將每一個大格子都可以拆分看成幾個小格子，先將最開始的數字進行填入，使每一個對應小格子的值都為大格子對應的數，搜索找到符合要求的即可

（答案：50 33 30 41）

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
bool vis[N];
int mp[N][N];
int a[50] = {0, 2, 5, 9, 11, 16, 17, 19, 21, 22, 24, 26, 30, 31, 33, 35, 36, 41, 50, 52};
void fill(int x, int y, int n, int a)
{for(int i = x; i < x + n; i ++){for(int j = y; j < y + n; j ++){mp[i][j] = a;}}
}
bool check()
{for(int i = 1; i <= 154; i ++){for(int j = 1; j <= 154; j ++){if(mp[i][j] == 0)return false;}}return true;
}
bool che(int x, int y, int n)
{if(x + n - 1 > 154 || y + n - 1 > 154)return false;for(int i = x; i < x + n; i ++){for(int j = y; j < y + n; j ++){if(mp[i][j])return false;}}return true;
}
bool dfs(int x, int y)
{if(check())return true;bool flag = true;for(int i = 1; i <= 154 && flag; i ++){for(int j = 1; j <= 154 && flag; j ++){if(mp[i][j] == 0){x = i;y = j;flag = false;}}}for(int k = 1; k <= 19; k ++){if(vis[k])continue;if(che(x, y, a[k])){fill(x, y, a[k], a[k]);vis[k] = true;if(dfs(x, y + a[k]))return true;fill(x, y, a[k], 0);vis[k] = false;}else return false;}return false;
}
int main()
{fill(1, 1, 47, 47);//在第一行第一列填充邊長為47格子的數字 fill(1, 48, 46, 46);//在第一行前47列填完后開始填第一行第48列長度為46格子的數字fill(1, 94, 61, 61);dfs(1, 1);int ans = 0;for(int i = 1; i <= 154; i ++)//輸出最后一行的每一列 {if(mp[154][i] != ans){ans = mp[154][i];cout << ans << ' ';	} } return 0;
}