列表

详情

NC214893. MineSweeperII

描述

A mine-sweeper map can be expressed as an grid. Each cell of the grid is either a mine cell or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the number of mine cells around it. (A cell is around another cell if they share at least one common point. Thus, every cell that is not on the boundary has 8 cells around it.) The following is a mine-sweeper map where a flagged cell denotes a mine cell and a blank cell denotes a non-mine cell with number 0.


Given two mine-sweeper maps of size , you should modify at most (i.e. the largest nonnegative integer that is less than or equal to ) cells in (from a non-mine cell to a mine cell or vice versa) such that the sum of numbers in the non-mine cells in and the sum of numbers in the non-mine cells in are the same. (If a map has no non-mine cell, the sum is considered as 0.)

If multiple solutions exist, print any of them. If no solution exists, print ''-1'' in one line.

输入描述

The first line contains two integers , denoting the size of given mine-sweeper maps.

The -th line of the following  lines contains a length- string consisting of  "." and "X" denoting the -th row of the mine-sweeper map . A "." denotes for a non-mine cell and an "X" denotes for a mine cell.

The -th line of the following  lines contains a length- string consisting of  "." and "X" denoting the -th row of the mine-sweeper map . A "." denotes for a non-mine cell and an "X" denotes for a mine cell.

输出描述

If no solution exists, print "-1" in one line.

Otherwise, print  lines denoting the modified mine-sweeper map . The -th line should contain a length- string consisting of  "." and "X" denoting the -th row of the modified map . A "." denotes for a non-mine cell and an "X" denotes for a mine cell.

Please notice that you need not print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map.

示例1

输入: 

2 4
X..X
X.X.
X.X.
.X..

输出: 

X.XX
.X..

说明:

We modify one cell in {B}. Then the sums of the numbers on non-mine cells in {A} and {B} both equal 10.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

pypy3(pypy3.6.1) 解法, 执行用时: 878ms, 内存消耗: 50020K, 提交时间: 2020-12-13 12:05:31 

n,m = map(int, input().split())
mp = []
for i in range(n):
    mp.append(input())

diff = 0

for i in range(n):
    tmp = input()
    for j, mono in enumerate(tmp):
        if mono != mp[i][j]:
            diff+=1

if diff <= (n*m)>>1:
    for i in mp:
        print(i)
else:
    for i in mp:
        for j in i:
            if j == 'X':
                print('.',end='')
            else:
                print('X',end='')
        print()

C++ 解法, 执行用时: 16ms, 内存消耗: 3328K, 提交时间: 2021-11-23 16:24:55 

#include<bits/stdc++.h>
using namespace std;
char a[1002][1002],b[1002][1002];
int main(){
	int n,m,s=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",a[i]);
	for(int i=1;i<=n;i++){
		scanf("%s",b[i]);
		for(int j=0;j<m;j++) s+=a[i][j]!=b[i][j];
	}
	if(s<=n*m/2) for(int i=1;i<=n;i++) puts(a[i]);
	else for(int i=1;i<=n;i++,puts("")) for(int j=0;j<m;j++) putchar(a[i][j]=='.'?'X':'.');
}

Python3(3.9) 解法, 执行用时: 248ms, 内存消耗: 10068K, 提交时间: 2020-12-24 23:36:48 

n,m=map(int,input().split())
ls=[input() for i in range(n)]
lcur=[input() for i in range(n)]
linv=map(lambda s:s.replace("X","Y").replace(".","X").replace("Y","."),ls)
cnt=0
for i in range(n):
    for j in range(m):
        if ls[i][j]==lcur[i][j]:
            cnt+=1
if n*m-cnt<=n*m//2:
    print("\n".join(ls))
else:
    print("\n".join(linv))

上一题

© 2025 nowcoder.com