blablabla
没啥好说的,记录自己写了两个小时写过的大模拟。
C++ 代码
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int N = 1000 + 10;
int n, m;
char g[N][N]; //*为地雷,.表示安全
int fg[N][N], tanming[N][N], a[N][N];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
bool ed = 0;
int total_step, yitanming, sum_anquan;
vector<pii> ans ;
void feedback(vector<pii> &p)
{
if (p.empty())
{
cout << "no cell detected\n";
return;
}
cout << (int)p.size() << " cell(s) detected\n";
sort(p.begin(), p.end());
for (auto &t : p)
{
cout << t.first << ' ' << t.second << ' ' << a[t.first][t.second] << '\n';
}
}
void jieshu(int state)
{
ed = 1;
if (state == 1)
cout << "finish\n";
if (state == 2)
cout << "game over\n";
if (state == 3)
cout << "give up\n";
cout << "total step " << total_step << '\n';
return;
}
void saolei(int x, int y)
{
if (ed)
return ;
if (g[x][y] == '*')
{
cout << "boom\n";
jieshu(2);
return ;
}
++yitanming;
tanming[x][y] = 1;
ans.push_back({x, y});
int cnt = 0;
for (int i = 0; i < 8; ++i)
{
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (g[xx][yy] == '*')
++cnt;
}
}
a[x][y] = cnt;
if (!a[x][y])
{
for (int i = 0; i < 8; ++i)
{
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (!tanming[xx][yy] )
{
fg[xx][yy] = 0;
tanming[xx][yy] = 1;
saolei(xx, yy);
if (ed)
return ;
}
}
}
}
}
void flag(int x, int y)
{
if (ed)
return;
if (tanming[x][y])
{
cout << "swept\n";
}
else
{
if (!fg[x][y])
{
fg[x][y] = 1;
cout << "success\n";
}
else
{
fg[x][y] = 0;
cout << "cancelled\n";
}
}
}
void sweep(int x, int y)
{
if (ed)
return;
if (tanming[x][y])
{
cout << "swept\n";
}
else if (fg[x][y])
cout << "flagged\n";
else if (!tanming[x][y])
{
saolei(x, y);
if (ed)
return;
feedback(ans);
}
if (yitanming == sum_anquan)
jieshu(1);
}
void dsweep(int x, int y)
{
if (ed)
return;
if (!tanming[x][y])
{
cout << "not swept\n";
return;
}
int cnt = 0;
for (int i = 0; i < 8; ++i)
{
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (fg[xx][yy])
++cnt;
}
}
if (!a[x][y] || a[x][y] != cnt)
{
cout << "failed\n";
return;
}
else
{
for (int i = 0; i < 8; ++i)
{
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (!fg[xx][yy] && !tanming[xx][yy])
{
saolei(xx, yy);
if (ed)
return;
}
}
}
}
feedback(ans);
if (yitanming == sum_anquan)
jieshu(1);
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> g[i] + 1;
for (int j = 1; j <= m; ++j)
{
if (g[i][j] == '.')
++sum_anquan;
}
}
string s;
while (cin >> s && s != "Quit")
{
int x, y;
cin >> x >> y;
++total_step;
ans.clear() ;
if (s == "Flag")
{
flag(x, y);
}
else if (s == "Sweep")
{
sweep(x, y);
}
else if (s == "DSweep")
{
dsweep(x, y);
}
if (ed)
return 0;
}
jieshu(3);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla