软件开发和网站建设那个好,自己做博客网站好,手机优化电池充电是什么意思,西安免费网站制作很有意思#xff0c;很好的题目。 这样的#xff0c;一个n*m的扫雷地图#xff0c;告诉你哪些地方是有雷的。一个人如果点在了空白处#xff0c;那么与其相邻的#xff08;八个方向#xff09;的数字以及空白都会递归地显示出来#xff0c;如果点在数字上面#xff0c;… 很有意思很好的题目。 这样的一个n*m的扫雷地图告诉你哪些地方是有雷的。一个人如果点在了空白处那么与其相邻的八个方向的数字以及空白都会递归地显示出来如果点在数字上面那么就只会显示这一个数字。 游戏过程中谁第一个无法点开一个非雷的格子算输。 这、、、、其实可以看成是nim博弈问题但是有一点点点点的不同。 我们由于题目说明了数字的部分不会有重复的所以我们把一个由空白部分连成的区域看成是一堆石子那么有的单独的数字就是一堆石子且只有一颗。 同时我们把所有的空白区域看成是一个石子这样问题就转化为了给你N堆石子以及每一堆的石子的数量现在要你求出博弈的结果是先手胜还是后手胜 由于每次可选择的可以使一堆中的某一颗石子也可以是一整堆的石子所以这与单纯的nim博弈是有所区别的。 其实可以这样来考虑这个问题。 我们分别统计出石子数量为奇数的堆有多少个x、石子数为偶数的堆有多少个y。 那么其实除非x和y均为偶数否则先手必胜。 这样来理解其实博弈过程中必胜者只要一直维护所有的石子数之和为偶数即可。 但是如果是一开始就为偶数偶数的话那么就是必输了。 不知道这么理解对不对呢 #pragma comment(linker, /STACK:1024000000,1024000000)
#include iostream
#include cstdio
#include cstring
#define maxn 1010
using namespace std;int a[maxn][maxn],t,n,m,k,xi,yi,ans,cas0,tot,flag;
bool b[maxn][maxn],vis[maxn][maxn];int dfs(int x,int y)
{if (a[x][y]-1 || x1 || xn || y1 || ym) return 0;if (b[x][y]) return 0;b[x][y]true;if (a[x][y]!0) return 1;return dfs(x1,y)dfs(x-1,y)dfs(x,y1)dfs(x,y-1)dfs(x-1,y-1)dfs(x-1,y1)dfs(x1,y-1)dfs(x1,y1);
}int main()
{scanf(%d,t);while (t--){memset(a,0,sizeof a);memset(b,false,sizeof b);memset(vis,false,sizeof vis);scanf(%d%d%d,n,m,k);tot0;while (k--){scanf(%d%d,xi,yi);xi1,yi1;vis[xi][yi]true;}for (int i1; in; i)for (int j1; jm; j){if (vis[i][j]){a[i][j]-1;continue;}a[i][j]0;for (int ii-1; ii1; ii)for (int jj-1; jj1; jj)if (vis[iii][jjj]) a[i][j];}ans0;for (int i1; in; i)for (int j1; jm; j){if (b[i][j]) continue;if (a[i][j]0){int tepdfs(i,j)1;if (tep1) ans^1;else ans^2;tot;}}for (int i1; in; i)for (int j1; jm; j){if (b[i][j]) continue;if (a[i][j]-1) continue;b[i][j]true;ans^1;tot;}if (ans) printf(Case #%d: Xiemao\n,cas);else printf(Case #%d: Fanglaoshi\n,cas);}return 0;
} 转载于:https://www.cnblogs.com/lochan/p/3450189.html
