2018山东省赛 H Dominoes ( 搜索 )
2024-09-05 17:59:02
题意 : 给出一个 n * m 的矩阵,用规格 1 * 2 的多米诺去填充,题目数据保证最后只有一个格子是空白的(即没有被多米诺骨牌覆盖),问你现在通过移动多米诺能够产生多少种不同的状态(空白位置作为状态依据,所以最多只有 n * m 种状态)
分析 :
这题看着很吓人,一般来说不会想到直接去搜索
因为要证明若走出环,能不能拓展出更多的状态
这个貌似是不存在的,若空白的地方经过重重移动回到了原点
那么必定不能产生更多的状态了,所以直接搜就行了
至于怎么证明......我没有搜到更好的题解解释,看到了再来填坑吧....
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define scs(i) scanf("%s", i) #define sci(i) scanf("%d", &i) #define scd(i) scanf("%lf", &i) #define scl(i) scanf("%lld", &i) #define scIl(i) scanf("%I64d", &i) #define scii(i, j) scanf("%d %d", &i, &j) #define scdd(i, j) scanf("%lf %lf", &i, &j) #define scll(i, j) scanf("%lld %lld", &i, &j) #define scIll(i, j) scanf("%I64d %I64d", &i, &j) #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k) #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k) #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k) #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define lowbit(i) (i & (-i)) #define mem(i, j) memset(i, j, sizeof(i)) #define fir first #define sec second #define ins(i) insert(i) #define pb(i) push_back(i) #define pii pair<int, int> #define mk(i, j) make_pair(i, j) #define all(i) i.begin(), i.end() #define pll pair<long long, long long> using namespace std; ; , , -, }; , , , }; , n, m, k, G[][maxn]; set<pii> s; void PRINT() { ; i<=n; i++){ ; j<=m; j++){ ) printf("- "); else printf("%d ", G[i][j]); }puts(""); }puts(""); } bool bound(int r, int c) { || c< || r>n || c>m); } void DFS(int r, int c) { //PRINT(); if(s.count(mk(r, c))) return; else s.ins(mk(r, c)); ; i<; i++){ ){ int _1 = c + dc[i]; *dc[i]; if(bound(r, _1)) continue; if(bound(r, _2)) continue; if(G[r][_1] == G[r][_2]){ G[r][_2] = -; G[r][c] = G[r][_1]; DFS(r, _2); G[r][_2] = G[r][_1]; G[r][c] = -; } }){ int _1 = r + dr[i]; *dr[i]; if(bound(_1, c)) continue; if(bound(_2, c)) continue; if(G[_1][c] == G[_2][c]){ G[_2][c] = -; G[r][c] = G[_1][c]; DFS(_2, c); G[_2][c] = G[_1][c]; G[r][c] = -; } } } } int main(void) { while(~sciii(n, m, k)){ mem(G, -); s.clear(); ; i<k; i++){ int r1, c1; int r2, c2; scii(r1, c1); scii(r2, c2); G[r1][c1] = cnt; G[r2][c2] = cnt++; } ; ; i<=n; i++){ ; j<=m; j++) ){ st_r = i; st_c = j; Find = ; break; } if(Find) break; } DFS(st_r, st_c); printf(); } ; }
最新文章
- 节省Json流量
- IE7,6与Fireofx的CSS兼容性处理方法集结
- 【转载】linux内核启动android文件系统过程分析
- 过滤掉combobox里名称相同的选项
- iOS delegate, 代理/委托与协议.
- 【CITE】C#目录、文件、文件夹操作
- win7防火墙打不开(无法启动windows firewall服务)
- LINQ.CS
- struts2初印象
- Effective C++_笔记_条款06_若不想使用编译器自动生成的函数,就该明确拒绝
- Yii2中DAO
- 剑指Offer——携程笔试题+知识点总结
- 【深度学习】--DCGAN从入门到实例应用
- php普通传值和引用传值 (相当通俗易懂的一篇讲解)
- [转]ANTS Performance Profiler和ANTS Memory Profiler 使用
- [No0000155]为什么32位机器最大只能用到4GB内存
- git时光机操作
- 手工Ghost安装系统
- Magento错误 Illegal scheme supplied, only alphanumeric characters are permitted
- has to be escaped using backslash to be included in string value\n