栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3377 Ancient Duper

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3377 Ancient Duper

#include<cstdio>#include<map>#define oo 123456789using namespace std;int n, m;map<pair<int, int>, int> mymap;inline bool isOne(int val, int idx) {return (val & (1 << idx)) != 0;}int dfs(int mp, int player) {pair<int, int> state = make_pair(mp, player);if (mymap.count(state)) {return mymap[state];} else {int i, j, k, l;int tmp;int res;if (player == 0) {res = -oo;} else {res = oo;}for (i = 0; i < n; i++) {for (j = 0; j < m - 2; j++) {if (isOne(mp, i * m + j) && isOne(mp, i * m + j + 1)) {for (k = j + 2; k < m; k++) {if (!isOne(mp, i * m + k)) {break;}}if (k >= m) {continue;}tmp = mp;for (l = j; l <= k; l++) {tmp ^= 1 << (i * m + l);}if (player == 0) {res = max(res, dfs(tmp, player ^ 1));} else {res = min(res, dfs(tmp, player ^ 1));}}}}for (i = 0; i < n; i++) {for (j = 2; j < m; j++) {if (isOne(mp, i * m + j) && isOne(mp, i * m + j - 1)) {for (k = j - 2; k >= 0; k--) {if (!isOne(mp, i * m + k)) {break;}}if (k < 0) {continue;}tmp = mp;for (l = k; l <= j; l++) {tmp ^= 1 << (i * m + l);}if (player == 0) {res = max(res, dfs(tmp, player ^ 1));} else {res = min(res, dfs(tmp, player ^ 1));}}}}for (i = 0; i < n - 2; i++) {for (j = 0; j < m; j++) {if (isOne(mp, i * m + j) && isOne(mp, (i + 1) * m + j)) {for (k = i + 2; k < n; k++) {if (!isOne(mp, k * m + j)) {break;}}if (k >= n) {continue;}tmp = mp;for (l = i; l <= k; l++) {tmp ^= 1 << (l * m + j);}if (player == 0) {res = max(res, dfs(tmp, player ^ 1));} else {res = min(res, dfs(tmp, player ^ 1));}}}}for (i = 2; i < n; i++) {for (j = 0; j < m; j++) {if (isOne(mp, i * m + j) && isOne(mp, (i - 1) * m + j)) {for (k = i - 2; k >= 0; k--) {if (!isOne(mp, k * m + j)) {break;}}if (k < 0) {continue;}tmp = mp;for (l = k; l <= i; l++) {tmp ^= 1 << (l * m + j);}if (player == 0) {res = max(res, dfs(tmp, player ^ 1));} else {res = min(res, dfs(tmp, player ^ 1));}}}}mymap[state] = res;return res;}}int main() {int i, j;char ch;int mp;while (~scanf("%d%d", &n, &m)) {mymap.clear();mp = 0;for (i = 0; i < n; i++) {for (j = 0; j < m; j++) {scanf(" %c", &ch);if (ch == 'e') {mp |= 1 << (i * m + j);}}}if (dfs(mp, 0) > 0) {puts("Tewi first");} else {puts("Reisen first");}}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/375312.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号