這里貼下不用枚舉方格是否為雷的方法
a表示輸入標(biāo)號，初始值為-1代表未探知
b表示當(dāng)前格子是否有雷,初始化為0,0表示未探知,1表示探知肯定有雷，2表示探知肯定無雷(我也不知道為什么不初始化為-1，作死。。。)
。。。二是個(gè)坑啊，不能用多余的想法解題。。。也就是3個(gè)條件不能互影響，不能用別的條件得出來的b的值，大概就是全寫成通過a的值來判斷
一二三都是通過數(shù)字和周邊已經(jīng)確定的雷數(shù)的關(guān)系來的，比如數(shù)字為5，周邊肯定5個(gè)雷，3個(gè)無雷，也用了集合包含來判斷
二三中隊(duì)列跳出的條件就是一輪下來，所有的未解決的數(shù)量都沒發(fā)生變化
那么接著弄也不會(huì)有變化了。
有按更新周圍格子不斷更新外圍可能修改的進(jìn)行優(yōu)化，也有按剩余探索格子數(shù)的優(yōu)先隊(duì)列進(jìn)行優(yōu)化
一

#include <cstdio> #include <memory> #include <cstdlib> #include <cstring> #include <cmath> #include <vector> #include <cassert> #include <string> #include <ctime> #include <map> #include <queue> #include <algorithm> #include <iostream> #include <cassert> #include <stack> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(i,a,b) for(int i=a;i<=b;i++) #define req(i,a,b) for(int i=a;i>=b;i--) #define rp(i,a) for(int i=head[a];i+1;i=edge[i].next) #define cl(a,b) memset(a,b,sizeof a); #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define mod 1000000007 const int inf = ~0u >> 2; const ll INF = (1LL << 62) - 1; double eps = 1e-9; const int N = 1e6 + 5; const int M = 221;int ans = 0, cnt = 0; int n, m; char str[M]; int a[N],b[N];void getsure() {for (int i = 3; i <= n; i+=3) {b[i] = (a[i-1] - a[i - 2]+(b[i-3]==2?0:1))==0?2:1;} } void getless() {for (int i = 1; i <= n; i++) {if (a[i] == 1) {if (b[i - 1] == 1) {b[i] = b[i + 1] = 2;}if (b[i] == 1) {b[i - 1] = b[i + 1] = 2;}if (b[i + 1] == 1) {b[i - 1] = b[i] = 2;}if (b[i - 1] == b[i] && b[i] == 2) {b[i + 1] = 1;}if (b[i - 1] == b[i + 1] && b[i - 1] == 2) {b[i] = 1;}if (b[i] == b[i + 1] && b[i] == 2) {b[i - 1] = 1;}}else if (a[i] == 2) {if (b[i - 1] == 2) {b[i] = b[i + 1] = 1;}if (b[i] == 2) {b[i - 1] = b[i + 1] = 1;}if (b[i + 1] == 2) {b[i - 1] = b[i] = 1;}if (b[i - 1] == b[i] && b[i] == 1) {b[i + 1] = 2;}if (b[i - 1] == b[i + 1] && b[i - 1] == 1) {b[i] = 2;}if (b[i] == b[i + 1] && b[i] == 1) {b[i - 1] = 2;}}} } int main() {int t;cin >> t;while (t--) {memset(a, 0, sizeof a);memset(b, 0, sizeof b);cin >> n;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}b[0] = b[n + 1] = 2;for (int i = 1; i <= n; i++) {if (a[i] == 3)b[i - 1] = b[i] = b[i + 1] = 1;}for (int i = 1; i <= n; i++) {if (a[i] == 0)b[i - 1] = b[i] = b[i + 1] = 2;}getsure();reverse(a + 1, a + n+1);reverse(b + 1, b + n+1);getsure();reverse(a + 1, a + n+1);reverse(b + 1, b + n+1);getless();reverse(a + 1, a + n+1);reverse(b + 1, b + n+1);getless();reverse(a + 1, a + n+1);reverse(b + 1, b + n+1);int cnt1 = 0;for(int i=1;i<=n;i++)if (b[i] == 1) {cnt1++;}printf("%d", cnt1);for (int i = 1; i <= n; i++)if (b[i] == 1)printf(" %d", i);printf("\n");int cnt2 = 0;for (int i = 1; i <= n; i++)if (b[i] == 2)cnt2++;printf("%d", cnt2);for (int i = 1; i <= n; i++) {if (b[i] == 2)printf(" %d", i);}printf("\n");}return 0; }

二

#include <cstdio> #include <memory> #include <cstdlib> #include <cstring> #include <cmath> #include <vector> #include <cassert> #include <string> #include <ctime> #include <map> #include <queue> #include <algorithm> #include <iostream> #include <cassert> #include <stack> #include <set> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(i,a,b) for(int i=a;i<=b;i++) #define req(i,a,b) for(int i=a;i>=b;i--) #define rp(i,a) for(int i=head[a];i+1;i=edge[i].next) #define cl(a,b) memset(a,b,sizeof a); #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define mod 1000000007 const int inf = ~0u >> 2; const ll INF = (1LL << 62) - 1; double eps = 1e-9; const int N = 2e2 + 5; const int M = 221;int ans = 0, cnt = 0; int n, m; char str[M]; int dx[] = {1,1,1,-1,-1,-1,0,0}; int dy[] = {0,1,-1,0,1,-1,1,-1}; int a[N][N],b[N][N]; void setval(int i, int j, int val);void getinit() {for(int i=1;i<=n;i++)for (int j = 1; j <= m; j++) {if (a[i][j] == 0) {for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (a[ni][nj] == -1)setval(ni, nj, 2);}}} } void setk(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m)return;int k = a[i][j];if (a[i][j] != -1) {int asum = 0;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (a[ni][nj] == -1)asum += 1;}if (asum == k) {for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];setval(ni, nj, 1);}}} } bool isok(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m)return false;return true; } void setval(int i, int j,int value) {if (i <= 0 || j <= 0 || i > n || j > m)return;if (a[i][j]==-1) {if (b[i][j] == 0) {b[i][j] = value;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];setk(ni, nj);}}} }struct Node {int x, y, d;int operator <(const Node& rhs)const {return d > rhs.d;} }; priority_queue<Node> q; int getsum(int i, int j,int c) {if (i <= 0 || j <= 0 || i > n || j > m) {//printf("-1!!\n");return -1;}int sum = 0;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (b[ni][nj] == c&&a[ni][nj]==-1) {sum++;}}return sum; } bool isdealed(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m) {//printf("-2!!\n");return -1;}if (a[i][j] == -1)return true;if (a[i][j] == 0)return true;if (getsum(i, j, 0) == 0)return true;return false; } set<pair<int, int>> getpairs(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m) {//printf("-3!!\n");return set<pair<int, int>>{};}set<pair<int, int>> pairs;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (a[ni][nj]==-1)pairs.insert(make_pair(ni, nj));}return pairs; } bool iscontain(set<pair<int, int>> pairs, set<pair<int, int>> xpairs) {if (pairs.size() <= xpairs.size())return false;bool exist = true;for (auto var : xpairs){if (pairs.count(var)==0) {exist = false;}}return exist; } void dealcontain(set<pair<int, int>> pairs, set <pair<int, int>> xpairs) {for (auto var : pairs){if (xpairs.count(var) == 0)setval(var.first, var.second, 1);} } void getcontain() {int qcnt = 0;while (!q.empty())q.pop();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (a[i][j] != -1&&!isdealed(i,j)) {q.push(Node{ i,j,getsum(i,j,0) });qcnt++;}}}int outtime = q.size();int curtime = 0;while (!q.empty()) {Node x = q.top(); q.pop();int sum = getsum(x.x, x.y, 0);set<pair<int, int>> xpairs = getpairs(x.x, x.y);vector<Node> surx;for (int i = x.x - 2; i <= x.x + 2; i++) {for (int j = x.y - 2; j <= x.y + 2; j++) {if (!isok(i, j)||i==x.x&&j==x.y)continue;if (a[i][j] != -1) {set<pair<int, int>> pairs = getpairs(i, j);if (iscontain(xpairs, pairs) && a[x.x][x.y] == a[i][j] + (xpairs.size() - pairs.size())) {dealcontain(xpairs, pairs);}}}}if (!isdealed(x.x,x.y)){if (getsum(x.x, x.y, 0) == sum) {q.push(Node{ x.x,x.y,qcnt++ });}else{q.push(Node{ x.x,x.y,getsum(x.x,x.y,0) });}curtime++;}else{outtime = q.size();curtime = 0;}if (curtime == outtime+1) {break;}}} int main() {int t;cin >> t;while (t--) {memset(a, 0, sizeof a);memset(b, 0, sizeof b);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &a[i][j]);}}getinit();for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)setk(i, j);getcontain();int cnt1 = 0;for(int i=1;i<=n;i++)for (int j = 1; j <= m; j++) {if (b[i][j] == 1&&a[i][j]==-1) {cnt1++;}}int cnt2 = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {if (b[i][j] == 2&&a[i][j]==-1)cnt2++;}printf("%d %d", cnt1,cnt2);printf("\n");}return 0; }

三

#include <cstdio> #include <memory> #include <cstdlib> #include <cstring> #include <cmath> #include <vector> #include <cassert> #include <string> #include <ctime> #include <map> #include <queue> #include <algorithm> #include <iostream> #include <cassert> #include <stack> #include <set> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(i,a,b) for(int i=a;i<=b;i++) #define req(i,a,b) for(int i=a;i>=b;i--) #define rp(i,a) for(int i=head[a];i+1;i=edge[i].next) #define cl(a,b) memset(a,b,sizeof a); #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define mod 1000000007 const int inf = ~0u >> 2; const ll INF = (1LL << 62) - 1; double eps = 1e-9; const int N = 2e2 + 5; const int M = 221;int ans = 0, cnt = 0; int n, m; char str[M]; int dx[] = {1,1,1,-1,-1,-1,0,0}; int dy[] = {0,1,-1,0,1,-1,1,-1}; int a[N][N],b[N][N]; void setval(int i, int j, int val);void getinit() {for(int i=1;i<=n;i++)for (int j = 1; j <= m; j++) {if (a[i][j] == 0) {for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];//if (a[ni][nj] == -1)setval(ni, nj, 2);}}if (a[i][j] == 8) {for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];setval(ni, nj, 1);}}} } void setk(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m)return;int k = a[i][j];if (a[i][j] != -1) {int asum = 0;int bsum0 = 0;int bsum1 = 0;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (a[ni][nj] == -1)asum += 1;if (b[ni][nj] == 1)bsum1 += 1;if (b[ni][nj] == 0)bsum0 += 1;}if (bsum1 == k) {for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (b[ni][nj] == 0)setval(ni, nj, 2);}}if (bsum1+bsum0==k) {for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (b[ni][nj] == 0)setval(ni, nj, 1);}}} } bool isok(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m)return false;return true; } void setval(int i, int j,int value) {if (i < 0 || j <= 0 || i > n || j > m)return;//if (a[i][j]==-1) {if (b[i][j] == 0) {b[i][j] = value;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];setk(ni, nj);}}//} }struct Node {int x, y, d;int operator <(const Node& rhs)const {return d > rhs.d;} }; priority_queue<Node> q; int getsum(int i, int j,int c) {if (i <= 0 || j <= 0 || i > n || j > m) {//printf("-1!!\n");return -1;}int sum = 0;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (b[ni][nj] == c/*&&a[ni][nj]==-1*/) {sum++;}}return sum; } bool isdealed(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m) {//printf("-2!!\n");return -1;}if (a[i][j] == -1)return true;if (a[i][j] == 0)return true;if (getsum(i, j, 0) == 0)return true;return false; } set<pair<int, int>> getpairs(int i, int j) {if (i <= 0 || j <= 0 || i > n || j > m) {//printf("-3!!\n");return set<pair<int, int>>{};}set<pair<int, int>> pairs;for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];//if (a[ni][nj]==-1)if(b[ni][nj]==0)pairs.insert(make_pair(ni, nj));}return pairs; } bool iscontain(set<pair<int, int>> pairs, set<pair<int, int>> xpairs) {if (pairs.size() <= xpairs.size())return false;bool exist = true;for (auto var : xpairs){if (pairs.count(var)==0) {exist = false;}}return exist; } void dealcontain(set<pair<int, int>> pairs, set <pair<int, int>> xpairs) {for (auto var : pairs){if (xpairs.count(var) == 0)setval(var.first, var.second, 1);} } void getcontain() {int qcnt = 0;while (!q.empty())q.pop();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (a[i][j] != -1&&!isdealed(i,j)) {q.push(Node{ i,j,getsum(i,j,0) });qcnt++;}}}int outtime = q.size();int curtime = 0;while (!q.empty()) {Node x = q.top(); q.pop();int sum = getsum(x.x, x.y, 0);set<pair<int, int>> xpairs = getpairs(x.x, x.y);vector<Node> surx;for (int i = x.x - 2; i <= x.x + 2; i++) {for (int j = x.y - 2; j <= x.y + 2; j++) {if (!isok(i, j)||i==x.x&&j==x.y)continue;if (a[i][j] != -1) {set<pair<int, int>> pairs = getpairs(i, j);if (iscontain(xpairs, pairs) && a[x.x][x.y]-getsum(x.x,x.y,1) == a[i][j]-getsum(i,j,1) + (xpairs.size() - pairs.size())) {dealcontain(xpairs, pairs);}}}}if (!isdealed(x.x,x.y)){if (getsum(x.x, x.y, 0) == sum) {q.push(Node{ x.x,x.y,qcnt++ });}else{q.push(Node{ x.x,x.y,getsum(x.x,x.y,0) });}curtime++;}else{outtime = q.size();curtime = 0;}if (curtime == outtime+1) {break;}}} int main() {int t;cin >> t;while (t--) {memset(a, -1, sizeof a);memset(b, 0, sizeof b);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &a[i][j]);if (a[i][j] != -1)//b[i][j] = 2;setval(i, j, 2);}}for (int i = 0; i <= n + 1; i++) {//setval(i, 0, 2);//setval(i, m + 1, 2);b[i][0] = b[i][m + 1] = 2;}for (int i = 0; i <= m + 1; i++) {//setval(0, i, 2);//setval(n + 1, i, 2);b[0][i] = b[n + 1][i] = 2;}getinit();for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)setk(i, j);getcontain();int cnt1 = 0;for(int i=1;i<=n;i++)for (int j = 1; j <= m; j++) {if (b[i][j] == 1&&a[i][j]==-1) {cnt1++;}}int cnt2 = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {if (b[i][j] == 2&&a[i][j]==-1)cnt2++;}printf("%d %d", cnt1,cnt2);printf("\n");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/HaibaraAi/p/6272219.html

總結(jié)

以上是生活随笔為你收集整理的Hihocoder 小Hi小Ho扫雷作死一二三的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。