Mine Sweeper II

題意：

給你兩個大小為 n * m 的掃雷圖 A, B，要求通過最多 n * m/2 次轉換（轉換指 把一個不是雷的格子變成雷， 或者把一個是雷的格子變成空白格），使得 B圖的值 和 A圖的值相等（值 就是指 掃雷圖上的所有數字之和，沒有數字或者雷的地方的值為0）
1≤n,m≤1000

題解：

一開始做時毫無思路，如果暴力下手肯定不行，有什么優化的地方
又一次仔細看題后，突然想到為什么題目要求最多轉換次數為n * m / 2，因為避免你將B全部都換一遍，而我們將A全部翻轉的到A’，發現A’的值和A是一樣的，而B在n * m / 2的交換次數下，是可以到A或者A’的，如果都不能到，那就輸出-1，否則輸出最近的一個

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1004; char a[maxn][maxn],b[maxn][maxn]; char ia[maxn][maxn]; int main() {int n,m;cin>>n>>m;char ch=getchar();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='X')ia[i][j]='.';else if(a[i][j]=='.')ia[i][j]='X';}char ch=getchar();}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>b[i][j];char ch=getchar();}int sum=0;int sum1=0;int ans=n*m/2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(b[i][j]!=a[i][j])sum++;if(b[i][j]!=ia[i][j])sum1++;}}if(sum>ans&&sum1>ans){cout<<-1;return 0;}if(sum<=ans){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j];}cout<<endl;}}else if(sum1<=ans){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<ia[i][j];}cout<<endl;}}return 0; }

總結

以上是生活随笔為你收集整理的Mine Sweeper II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。