寻找俄罗斯方块
寻找俄罗斯方块:
思路:记忆化BFS。直接匹配四种旋转情况,可直接AC
代码:
#include <iostream> #include <queue> using namespace std; typedef pair<int,int> PII; int n, m; int dirx[4] = {-1, 0, 1, 0}; int diry[4] = {0, -1, 0 ,1}; int main() { cin >> m >> n; vector<vector<int>> mp(m, vector<int> (n)); vector<vector<bool>> st(m, vector<bool> (n, false)); for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) cin >> mp[i][j]; for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) { if(mp[i][j] && !st[i][j]) { st[i][j] = true; int up = 0, down = 0, left = 0, right = 0; queue<PII> q; q.push({i, j}); while(q.size()) { auto t = q.front(); q.pop(); int x = t.first, y = t.second; for(int k = 0; k < 4; k++) { int nex = x + dirx[k], ney = y + diry[k]; if(nex >= 0 && nex < m && ney >= 0 && ney < n && !st[nex][ney] && mp[nex][ney]) { st[nex][ney] = true; if(k == 0) up++; if(k == 1) left++; if(k == 2) down++; if(k == 3) right++; q.push({nex, ney}); } } } //做匹配 if(down == 2 && right == 1 && left == 0 && up == 0) cout << i * n + j << " " << i * n + j + 1 << " " << (i + 1) * n + j << " " << (i + 2) * n + j << endl; if(down == 1 && right == 2 && left == 0 && up == 0) { if(mp[i+1][j]) cout << i * n + j << " " << (i + 1) * n + j << " " << (i + 1) * n + j + 1 << " " << (i + 1) * n + j + 2 << endl; else cout << i * n + j << " " << i * n + j + 1 << " " << i * n + j + 2 << " " << (i + 1) * n + j + 2 << endl; } if(down == 2 && left == 1 && right == 0 && up == 0) cout << i * n + j << " " << (i + 1) * n + j << " " << (i + 2) * n + j - 1 << " " << (i + 2) * n + j << endl; } } return 0; }