題目分析

來源：acwing

分析:

本題類似消消樂，同一行或者同一列滿足3個或者更多個同色的可以消除（數(shù)值置為0),由于數(shù)據(jù)量比較小，時間復(fù)雜度可以到$O(n^3)$.

這里是對每個點，統(tǒng)計和它同色的點，最左邊能到哪里，最右邊能到哪里，最上面能到哪里，最下面能到哪里。使用四個while循環(huán)。這是對每個點的操作，需要對圖中每個點都進行這種操作，在本題的數(shù)據(jù)量下，可以過。

AC代碼

#include<bits/stdc++.h> using namespace std; const int N = 40; int g[N][N]; bool st[N][N];int n, m;int main(){cin >> n >> m;for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)cin >> g[i][j];for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){int l = j, r = j, u = i, d = i, x = g[i][j];/*以找到3個2為例：下標(biāo)：0 1 2 3 4 5 6值： 1 2 2 2 3 2 4l的下標(biāo)：0r的下標(biāo)：4實際2的長度：3推出長度公式： r - l - 1*/while(l >= 0 && g[i][l] == x) l --; // 減到答案左邊1個格while(r < m && g[i][r] == x) r ++; // 加到答案右邊1個格while(u >= 0 && g[u][j] == x) u --;while(d < n && g[d][j] == x ) d ++;// 左右方向是否大于3，上下方向是否大于3st[i][j] = r - l -1 >= 3 || d - u - 1 >= 3;}}for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++)if(st[i][j]) cout << 0<<" ";else cout <<g[i][j] <<" ";cout << endl;} }

題目鏈接

https://www.acwing.com/problem/content/3226/

總結(jié)

以上是生活随笔為你收集整理的CSP认证201512-2消除类游戏[C++题解]：模拟的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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