本文由编程笔记#自由互联小编为大家整理,主要介绍了CQOI2013新数独相关的知识,希望对你有一定的参考价值。传送门这道题也是 本文由编程笔记#自由互联小编为大家整理,主要介绍了
本文由编程笔记#自由互联小编为大家整理,主要介绍了CQOI2013新数独相关的知识,希望对你有一定的参考价值。传送门这道题也是 本文由编程笔记#自由互联小编为大家整理,主要介绍了CQOI2013 新数独相关的知识,希望对你有一定的参考价值。
传送门
这道题也是很暴力的搜索啊……
因为数独一开始全是空的,只有许许多多的大小限制条件,那也没必要纠结从哪开始搜索了,直接暴力搜索之后判断一下是否合法。
这题最恶心的是读入。现学了一招判断点在哪个块内,用lim[g][i][j],表示在g宫内i和j这两个格子的大小关系,处理还是相当复杂的(代码里有),之后就没什么要注意的,全是爆搜。
最后这个爆搜还会T两个点,要开O2.我也想不到有什么更好的优化了……
看一下代码。
// luogu-judger-enable-o2#include#include#include#include#include#include#define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar(‘‘)using namespace std;typedef long long ll;const int M = 1005;const int mod = 1e9 + 7;int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch ‘9‘) { if(ch == ‘-‘) op = -1; ch = getchar(); } while(ch >= ‘0‘ ans += ch - ‘0‘; ch = getchar(); } return ans * op;}int num[11][11],hcnt,lcnt,px,py;int lim[11][11][11],vish[11][11],visl[11][11],visg[11][11];char s;void print(){ rep(i,1,9) { rep(j,1,9) printf("%d ",num[i][j]);enter; }}bool pd(int g,int pos,int k){ rep(j,1,9) { int dx = g / 3 * 3 + (j - 1) / 3 + 1,dy = g % 3 * 3 + (j - 1) % 3 + 1; if(lim[g][pos][j] == 1 if(lim[g][pos][j] == 2 } return 1;}void buildh(int i,int k){ rep(j,1,6) { int g = (i - 1) * 3 + ((j - 1) >> 1); int pos = ((k - 1) >> 1) * 3 + ((j - 1) cin >> s; lim[g][pos][pos+1] = (s == ‘>‘) ? 1 : 2; lim[g][pos+1][pos] = (s == ‘>‘) ? 2 : 1; }}void buildl(int i,int k){ rep(j,1,9) { int g = (i - 1) * 3 + (j - 1) / 3; int pos = ((k-1) >> 1) * 3 + (j - 1) % 3 + 1; cin >> s; lim[g][pos][pos+3] = (s == ‘v‘) ? 1 : 2; lim[g][pos+3][pos] = (s == ‘v‘) ? 2 : 1; }}void build(){ rep(i,1,3) rep(k,1,5) (k }void dfs(int x,int y){ int g = ((x - 1) / 3) * 3 + (y - 1) / 3; int pos = (x - 1) % 3 * 3 + (y - 1) % 3 + 1; rep(k,1,9) { if(vish[x][k] || visl[y][k] || visg[g][k]) continue; if(!pd(g,pos,k)) continue; vish[x][k] = visl[y][k] = visg[g][k] = 1,num[x][y] = k; //print(); if(x == 9 else (y == 9) ? dfs(x+1,1) : dfs(x,y+1); vish[x][k] = visl[y][k] = visg[g][k] = 0,num[x][y] = 0; }}int main(){ build(); /*rep(i,1,9) { rep(j,1,9) { printf("%d ",lim[1][i][j]); } enter; }*/ dfs(1,1); return 0;}