首页 > 代码库 > A Yellowstar的第一道题 博弈

A Yellowstar的第一道题 博弈

题目链接:点击打开链接

先来个暴力程序找下规律。

若n*r*c 是偶数,则是必败态,输出0.000000

否则对于3*3*3 赢的位置有:

1 0 1
0 1 0
1 0 1
0 1 0
1 0 1
0 1 0
1 0 1
0 1 0
1 0 1

1为必胜点。也就是说左上角是1,这样扩散出去。

答案就是所有1位置的概率和。

暴力程序:

#include <cstdio>
#include <cstring>

int n, m, d, step[6][3] = {0,0,1, 0,0,-1, 0,1,0, 0,-1,0, 1,0,0, -1,0,0};
bool inmap(int x, int y,int z){return 1<=x&&x<=n&&1<=y&&y<=m&&1<=z&&z<=d;}
bool vis[20][20][20];
bool dfs(int x, int y,int z){//0是先手
    vis[x][y][z] = 1;
    for(int i = 0; i < 6; i++)
    {
        int a = x + step[i][0], b = y + step[i][1], c = z + step[i][2];
        if(!inmap(a,b,c) || vis[a][b][c])continue;
        if(dfs(a,b,c))
        {
            vis[x][y][z] = 0;
            return false;
        }
    }
    vis[x][y][z] = 0;
    return true;
}
bool work(){
    memset(vis, 0, sizeof vis);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
        for(int k = 1; k <= d; k++)
            printf("%d ", dfs(i,j,k));
            puts("");
        }
}
int main(){
    while(~scanf("%d%d%d", &n, &m, &d))
        work();
    return 0;
}
ac代码:

#include <cstdio>
int main() {
	int n, r, c;
	while(~scanf("%d%d%d", &n, &r, &c)) {
		double x, sum = 0;
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= r; j ++) {
				for(int k = 1; k <= c; k ++) {
					scanf("%lf", &x);
					if((i + j + k) & 1) sum += x;
				}
			}
		}
		if((n*r*c) & 1) printf("%.6f\n", sum);
		else puts("0.000000");
	}
	return 0;
}



A Yellowstar的第一道题 博弈