MMT4. 大家来扫雷
描述
小M最近爱上了扫雷游戏，就是在一个n*m的区域中，有地雷，每一个方格上都有一个数字s，表示在这个方格周围有s颗雷，现在给你一张表明地雷的图，并且指定一个位置点开，请输出点开后的数字情况，若点开的地方的数字为0，则向该方格周围扩展，直到遇到数字或者地图边界为止，若点开的地方为地雷,那么直接输出"GG"。
周围指的是上，左上，左，左下，下，右下，右，右上八个方向。
输入描述
第一行有两个数字n和m(2<=n,m<=1000)，表示地图的大小，第二行有两个整数x和y(1<=x<=n,1<=y<=m)，表示点击第x行y列的方格，接下来的是一个n行m列的一个矩阵，表示地图，其中.表示空地，*表示地雷。输出描述
如果点开的地方为地雷直接输出"GG"。否则输出点击指定位置后的地图，"."表示未点开的空地，"*"表示地雷，数字表示在该方格周围的地雷数目。示例1
输入:
3 4 1 1 .... ..*. ....
输出:
01.. 01*. 01..
C++ 解法, 执行用时: 32ms, 内存消耗: 6264KB, 提交时间: 2020-10-31
// test.cpp : Defines the entry point for the console application.
//
//#define DEBUG
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000003
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define perll(i,a,b) for(ll i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, ll m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 405
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
#ifdef SEG_TREE
struct node {
int val;
}tree[N<<2];
bool flag[N>>1];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
flag[tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
#endif
#ifdef BTREE
#define lowbit(t) t&(-t)
int a[50005];
void Update(int i, int v, int n) {
while (i<=n) {
a[i]+=v;
i+=lowbit(i);
}
}
int Sum(int i) {
int res = 0;
while (i) {
res+=a[i];
i-=lowbit(i);
}
return res;
}
#endif
//int prime[1000005], sift[1000005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
//int fa[100005];
//int cnt[100005];
//
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
//}
//
//int Find(int x) {
// int y = x;
// while (x != fa[x]) {
// x = fa[x];
// }
// return fa[y] = x;
//}
//
//void Union(int x, int y) {
// x = Find(x), y = Find(y);
// if (x != y) {
// cnt[x] += cnt[y];
// fa[y] = x;
// }
//}
#ifdef UF
//int fa[100005];
//int cnt[100005];
unordered_map<int, int> fa, cnt, rnk;
int components;
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
// components = n;
//}
void Init(int n) {
if (!fa.count(n)) {
fa[n] = n;
cnt[n] = 1;
rnk[n] = 0;
++components;
}
}
int Find(int x) {
int y = x;
while (x != fa[x]) {
x = fa[x];
}
return fa[y] = x;
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x != y) {
if (rnk[x] > rnk[y]) {
fa[y] = x;
cnt[x] += cnt[y];
}
else {
fa[x] = y;
cnt[y] += cnt[x];
if (rnk[x] == rnk[y])
++rnk[y];
}
--components;
}
}
#endif
#ifdef BIG_OP
int o3[105], o1[105]={1}, o2[105]={2};
int l_o3 = 0, l_o1 = 1, l_o2 = 1;
int one[1] = {1};
int big_add(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int carry = 0;
int len = 0;
memset(res, 0, sizeof(int)*(max(l_op2, l_op1)+1));
repi(i,0,max(l_op2, l_op1)) {
int tmp = carry;
if (i<l_op1) {
tmp += op1[i];
}
if (i<l_op2) {
tmp += op2[i];
}
res[len++] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[len++] = carry;
}
return len;
}
int big_mul(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int len = l_op1+l_op2-1;
memset(res, 0, sizeof(int)*(len+1));
repi(i,0,l_op1) {
int carry = 0;
repi(j,0,l_op2) {
int tmp = res[i+j] + carry + op1[i] * op2[j];
res[i+j] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[i+l_op2] = carry;
len = max(i + l_op2+1, len);
}
}
return len;
}
int *res = o3, *op1 = o1, *op2 = o2, l_res = l_o3, l_op1 = l_o1, l_op2 = l_o2;
repi(i,1,n) {
l_res = big_mul(res, op1, op2, l_op1, l_op2);
swap(op1, res);
swap(l_op1, l_res);
// peri(t,l_op1-1,0) {
// printf("%d", op1[t]);
// }
// putchar('\n');
l_res = big_add(res, op2, one, l_op2, 1);
swap(op2, res);
swap(l_op2, l_res);
}
#endif
int dfs(int n) {
int res = 0;
int last = sqrt(n);
if (last & 1) {
res = last * (last + 1) >> 1;
} else {
res = last * (last - 1) >> 1;
res += (n - last * last + 1);
}
return res;
}
char str[1005][1005];
int num[1005][1005];
void cnt() {
repi(i,0,n) {
repi(j,0,m) {
if (str[i][j] == '*') {
repi(t,0,8) {
int xx = i+dx[t], yy = j+dy[t];
if (xx < 0 || xx >= n || yy < 0 || yy >= m || str[xx][yy] == '*') {
continue;
}
++num[xx][yy];
}
}
}
}
}
void sweep(int x, int y) {
queue<pii> q;
q.emplace(x,y);
str[x][y] = num[x][y]+'0';
while (!q.empty()) {
auto p = q.front();
q.pop();
if (num[p.x][p.y]) {
continue;
}
repi (i, 0, 8) {
int px = p.x + dx[i];
int py = p.y + dy[i];
if (px >= 0 && px < n && py >= 0 && py < m && str[px][py] == '.') {
q.emplace(px, py);
str[px][py] = num[px][py]+'0';
}
}
}
}
int main() {
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
while (T--)
// while (~scanf("%s", str))
// repi(c,1,T+1)
{
scanf("%d%d", &n, &m);
int x,y;
scanf("%d%d", &x, &y);
--x,--y;
repi(i,0,n) {
scanf("%s", str[i]);
}
if (str[x][y] == '*') {
puts("GG");
} else {
cnt();
sweep(x,y);
repi(i,0,n) {
puts(str[i]);
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif
C++ 解法, 执行用时: 33ms, 内存消耗: 6264KB, 提交时间: 2020-11-01
// test.cpp : Defines the entry point for the console application.
//
//#define DEBUG
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000003
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define perll(i,a,b) for(ll i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, ll m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 405
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
#ifdef SEG_TREE
struct node {
int val;
}tree[N<<2];
bool flag[N>>1];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
flag[tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
#endif
#ifdef BTREE
#define lowbit(t) t&(-t)
int a[50005];
void Update(int i, int v, int n) {
while (i<=n) {
a[i]+=v;
i+=lowbit(i);
}
}
int Sum(int i) {
int res = 0;
while (i) {
res+=a[i];
i-=lowbit(i);
}
return res;
}
#endif
//int prime[1000005], sift[1000005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
//int fa[100005];
//int cnt[100005];
//
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
//}
//
//int Find(int x) {
// int y = x;
// while (x != fa[x]) {
// x = fa[x];
// }
// return fa[y] = x;
//}
//
//void Union(int x, int y) {
// x = Find(x), y = Find(y);
// if (x != y) {
// cnt[x] += cnt[y];
// fa[y] = x;
// }
//}
#ifdef UF
//int fa[100005];
//int cnt[100005];
unordered_map<int, int> fa, cnt, rnk;
int components;
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
// components = n;
//}
void Init(int n) {
if (!fa.count(n)) {
fa[n] = n;
cnt[n] = 1;
rnk[n] = 0;
++components;
}
}
int Find(int x) {
int y = x;
while (x != fa[x]) {
x = fa[x];
}
return fa[y] = x;
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x != y) {
if (rnk[x] > rnk[y]) {
fa[y] = x;
cnt[x] += cnt[y];
}
else {
fa[x] = y;
cnt[y] += cnt[x];
if (rnk[x] == rnk[y])
++rnk[y];
}
--components;
}
}
#endif
#ifdef BIG_OP
int o3[105], o1[105]={1}, o2[105]={2};
int l_o3 = 0, l_o1 = 1, l_o2 = 1;
int one[1] = {1};
int big_add(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int carry = 0;
int len = 0;
memset(res, 0, sizeof(int)*(max(l_op2, l_op1)+1));
repi(i,0,max(l_op2, l_op1)) {
int tmp = carry;
if (i<l_op1) {
tmp += op1[i];
}
if (i<l_op2) {
tmp += op2[i];
}
res[len++] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[len++] = carry;
}
return len;
}
int big_mul(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int len = l_op1+l_op2-1;
memset(res, 0, sizeof(int)*(len+1));
repi(i,0,l_op1) {
int carry = 0;
repi(j,0,l_op2) {
int tmp = res[i+j] + carry + op1[i] * op2[j];
res[i+j] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[i+l_op2] = carry;
len = max(i + l_op2+1, len);
}
}
return len;
}
int *res = o3, *op1 = o1, *op2 = o2, l_res = l_o3, l_op1 = l_o1, l_op2 = l_o2;
repi(i,1,n) {
l_res = big_mul(res, op1, op2, l_op1, l_op2);
swap(op1, res);
swap(l_op1, l_res);
// peri(t,l_op1-1,0) {
// printf("%d", op1[t]);
// }
// putchar('\n');
l_res = big_add(res, op2, one, l_op2, 1);
swap(op2, res);
swap(l_op2, l_res);
}
#endif
int dfs(int n) {
int res = 0;
int last = sqrt(n);
if (last & 1) {
res = last * (last + 1) >> 1;
} else {
res = last * (last - 1) >> 1;
res += (n - last * last + 1);
}
return res;
}
char str[1005][1005];
int num[1005][1005];
void cnt() {
repi(i,0,n) {
repi(j,0,m) {
if (str[i][j] == '*') {
repi(t,0,8) {
int xx = i+dx[t], yy = j+dy[t];
if (xx < 0 || xx >= n || yy < 0 || yy >= m || str[xx][yy] == '*') {
continue;
}
++num[xx][yy];
}
}
}
}
}
void sweep(int x, int y) {
queue<pii> q;
q.emplace(x,y);
str[x][y] = num[x][y]+'0';
while (!q.empty()) {
auto p = q.front();
q.pop();
if (num[p.x][p.y]) {
continue;
}
repi (i, 0, 8) {
int px = p.x + dx[i];
int py = p.y + dy[i];
if (px >= 0 && px < n && py >= 0 && py < m && str[px][py] == '.') {
q.emplace(px, py);
str[px][py] = num[px][py]+'0';
}
}
}
}
int main() {
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
while (T--)
// while (~scanf("%s", str))
// repi(c,1,T+1)
{
scanf("%d%d", &n, &m);
int x,y;
scanf("%d%d", &x, &y);
--x,--y;
repi(i,0,n) {
scanf("%s", str[i]);
}
if (str[x][y] == '*') {
puts("GG");
} else {
cnt();
sweep(x,y);
repi(i,0,n) {
puts(str[i]);
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif
C++ 解法, 执行用时: 34ms, 内存消耗: 6268KB, 提交时间: 2020-10-31
// test.cpp : Defines the entry point for the console application.
//
//#define DEBUG
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000003
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define perll(i,a,b) for(ll i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, ll m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 405
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
#ifdef SEG_TREE
struct node {
int val;
}tree[N<<2];
bool flag[N>>1];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
flag[tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
#endif
#ifdef BTREE
#define lowbit(t) t&(-t)
int a[50005];
void Update(int i, int v, int n) {
while (i<=n) {
a[i]+=v;
i+=lowbit(i);
}
}
int Sum(int i) {
int res = 0;
while (i) {
res+=a[i];
i-=lowbit(i);
}
return res;
}
#endif
//int prime[1000005], sift[1000005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
//int fa[100005];
//int cnt[100005];
//
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
//}
//
//int Find(int x) {
// int y = x;
// while (x != fa[x]) {
// x = fa[x];
// }
// return fa[y] = x;
//}
//
//void Union(int x, int y) {
// x = Find(x), y = Find(y);
// if (x != y) {
// cnt[x] += cnt[y];
// fa[y] = x;
// }
//}
#ifdef UF
//int fa[100005];
//int cnt[100005];
unordered_map<int, int> fa, cnt, rnk;
int components;
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
// components = n;
//}
void Init(int n) {
if (!fa.count(n)) {
fa[n] = n;
cnt[n] = 1;
rnk[n] = 0;
++components;
}
}
int Find(int x) {
int y = x;
while (x != fa[x]) {
x = fa[x];
}
return fa[y] = x;
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x != y) {
if (rnk[x] > rnk[y]) {
fa[y] = x;
cnt[x] += cnt[y];
}
else {
fa[x] = y;
cnt[y] += cnt[x];
if (rnk[x] == rnk[y])
++rnk[y];
}
--components;
}
}
#endif
#ifdef BIG_OP
int o3[105], o1[105]={1}, o2[105]={2};
int l_o3 = 0, l_o1 = 1, l_o2 = 1;
int one[1] = {1};
int big_add(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int carry = 0;
int len = 0;
memset(res, 0, sizeof(int)*(max(l_op2, l_op1)+1));
repi(i,0,max(l_op2, l_op1)) {
int tmp = carry;
if (i<l_op1) {
tmp += op1[i];
}
if (i<l_op2) {
tmp += op2[i];
}
res[len++] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[len++] = carry;
}
return len;
}
int big_mul(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int len = l_op1+l_op2-1;
memset(res, 0, sizeof(int)*(len+1));
repi(i,0,l_op1) {
int carry = 0;
repi(j,0,l_op2) {
int tmp = res[i+j] + carry + op1[i] * op2[j];
res[i+j] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[i+l_op2] = carry;
len = max(i + l_op2+1, len);
}
}
return len;
}
int *res = o3, *op1 = o1, *op2 = o2, l_res = l_o3, l_op1 = l_o1, l_op2 = l_o2;
repi(i,1,n) {
l_res = big_mul(res, op1, op2, l_op1, l_op2);
swap(op1, res);
swap(l_op1, l_res);
// peri(t,l_op1-1,0) {
// printf("%d", op1[t]);
// }
// putchar('\n');
l_res = big_add(res, op2, one, l_op2, 1);
swap(op2, res);
swap(l_op2, l_res);
}
#endif
int dfs(int n) {
int res = 0;
int last = sqrt(n);
if (last & 1) {
res = last * (last + 1) >> 1;
} else {
res = last * (last - 1) >> 1;
res += (n - last * last + 1);
}
return res;
}
char str[1005][1005];
int num[1005][1005];
void cnt() {
repi(i,0,n) {
repi(j,0,m) {
if (str[i][j] == '*') {
repi(t,0,8) {
int xx = i+dx[t], yy = j+dy[t];
if (xx < 0 || xx >= n || yy < 0 || yy >= m || str[xx][yy] == '*') {
continue;
}
++num[xx][yy];
}
}
}
}
}
void sweep(int x, int y) {
queue<pii> q;
q.emplace(x,y);
str[x][y] = num[x][y]+'0';
while (!q.empty()) {
auto p = q.front();
q.pop();
if (num[p.x][p.y]) {
continue;
}
repi (i, 0, 8) {
int px = p.x + dx[i];
int py = p.y + dy[i];
if (px >= 0 && px < n && py >= 0 && py < m && str[px][py] == '.') {
q.emplace(px, py);
str[px][py] = num[px][py]+'0';
}
}
}
}
int main() {
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
while (T--)
// while (~scanf("%s", str))
// repi(c,1,T+1)
{
scanf("%d%d", &n, &m);
int x,y;
scanf("%d%d", &x, &y);
--x,--y;
repi(i,0,n) {
scanf("%s", str[i]);
}
if (str[x][y] == '*') {
puts("GG");
} else {
cnt();
sweep(x,y);
repi(i,0,n) {
puts(str[i]);
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif
C++ 解法, 执行用时: 35ms, 内存消耗: 7312KB, 提交时间: 2020-12-23
// test.cpp : Defines the entry point for the console application.
//
//#define DEBUG
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000003
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define perll(i,a,b) for(ll i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, ll m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 405
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
#ifdef SEG_TREE
struct node {
int val;
}tree[N<<2];
bool flag[N>>1];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
flag[tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
#endif
#ifdef BTREE
#define lowbit(t) t&(-t)
int a[50005];
void Update(int i, int v, int n) {
while (i<=n) {
a[i]+=v;
i+=lowbit(i);
}
}
int Sum(int i) {
int res = 0;
while (i) {
res+=a[i];
i-=lowbit(i);
}
return res;
}
#endif
//int prime[1000005], sift[1000005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
//int fa[100005];
//int cnt[100005];
//
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
//}
//
//int Find(int x) {
// int y = x;
// while (x != fa[x]) {
// x = fa[x];
// }
// return fa[y] = x;
//}
//
//void Union(int x, int y) {
// x = Find(x), y = Find(y);
// if (x != y) {
// cnt[x] += cnt[y];
// fa[y] = x;
// }
//}
#ifdef UF
//int fa[100005];
//int cnt[100005];
unordered_map<int, int> fa, cnt, rnk;
int components;
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
// components = n;
//}
void Init(int n) {
if (!fa.count(n)) {
fa[n] = n;
cnt[n] = 1;
rnk[n] = 0;
++components;
}
}
int Find(int x) {
int y = x;
while (x != fa[x]) {
x = fa[x];
}
return fa[y] = x;
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x != y) {
if (rnk[x] > rnk[y]) {
fa[y] = x;
cnt[x] += cnt[y];
}
else {
fa[x] = y;
cnt[y] += cnt[x];
if (rnk[x] == rnk[y])
++rnk[y];
}
--components;
}
}
#endif
#ifdef BIG_OP
int o3[105], o1[105]={1}, o2[105]={2};
int l_o3 = 0, l_o1 = 1, l_o2 = 1;
int one[1] = {1};
int big_add(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int carry = 0;
int len = 0;
memset(res, 0, sizeof(int)*(max(l_op2, l_op1)+1));
repi(i,0,max(l_op2, l_op1)) {
int tmp = carry;
if (i<l_op1) {
tmp += op1[i];
}
if (i<l_op2) {
tmp += op2[i];
}
res[len++] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[len++] = carry;
}
return len;
}
int big_mul(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int len = l_op1+l_op2-1;
memset(res, 0, sizeof(int)*(len+1));
repi(i,0,l_op1) {
int carry = 0;
repi(j,0,l_op2) {
int tmp = res[i+j] + carry + op1[i] * op2[j];
res[i+j] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[i+l_op2] = carry;
len = max(i + l_op2+1, len);
}
}
return len;
}
int *res = o3, *op1 = o1, *op2 = o2, l_res = l_o3, l_op1 = l_o1, l_op2 = l_o2;
repi(i,1,n) {
l_res = big_mul(res, op1, op2, l_op1, l_op2);
swap(op1, res);
swap(l_op1, l_res);
// peri(t,l_op1-1,0) {
// printf("%d", op1[t]);
// }
// putchar('\n');
l_res = big_add(res, op2, one, l_op2, 1);
swap(op2, res);
swap(l_op2, l_res);
}
#endif
int dfs(int n) {
int res = 0;
int last = sqrt(n);
if (last & 1) {
res = last * (last + 1) >> 1;
} else {
res = last * (last - 1) >> 1;
res += (n - last * last + 1);
}
return res;
}
char str[1005][1005];
int num[1005][1005];
void cnt() {
repi(i,0,n) {
repi(j,0,m) {
if (str[i][j] == '*') {
repi(t,0,8) {
int xx = i+dx[t], yy = j+dy[t];
if (xx < 0 || xx >= n || yy < 0 || yy >= m || str[xx][yy] == '*') {
continue;
}
++num[xx][yy];
}
}
}
}
}
void sweep(int x, int y) {
queue<pii> q;
q.emplace(x,y);
str[x][y] = num[x][y]+'0';
while (!q.empty()) {
auto p = q.front();
q.pop();
if (num[p.x][p.y]) {
continue;
}
repi (i, 0, 8) {
int px = p.x + dx[i];
int py = p.y + dy[i];
if (px >= 0 && px < n && py >= 0 && py < m && str[px][py] == '.') {
q.emplace(px, py);
str[px][py] = num[px][py]+'0';
}
}
}
}
int main() {
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
while (T--)
// while (~scanf("%s", str))
// repi(c,1,T+1)
{
scanf("%d%d", &n, &m);
int x,y;
scanf("%d%d", &x, &y);
--x,--y;
repi(i,0,n) {
scanf("%s", str[i]);
}
if (str[x][y] == '*') {
puts("GG");
} else {
cnt();
sweep(x,y);
repi(i,0,n) {
puts(str[i]);
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif
C++ 解法, 执行用时: 41ms, 内存消耗: 7296KB, 提交时间: 2020-12-19
// test.cpp : Defines the entry point for the console application.
//
//#define DEBUG
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000003
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define perll(i,a,b) for(ll i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, ll m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 405
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
#ifdef SEG_TREE
struct node {
int val;
}tree[N<<2];
bool flag[N>>1];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
flag[tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
#endif
#ifdef BTREE
#define lowbit(t) t&(-t)
int a[50005];
void Update(int i, int v, int n) {
while (i<=n) {
a[i]+=v;
i+=lowbit(i);
}
}
int Sum(int i) {
int res = 0;
while (i) {
res+=a[i];
i-=lowbit(i);
}
return res;
}
#endif
//int prime[1000005], sift[1000005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
//int fa[100005];
//int cnt[100005];
//
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
//}
//
//int Find(int x) {
// int y = x;
// while (x != fa[x]) {
// x = fa[x];
// }
// return fa[y] = x;
//}
//
//void Union(int x, int y) {
// x = Find(x), y = Find(y);
// if (x != y) {
// cnt[x] += cnt[y];
// fa[y] = x;
// }
//}
#ifdef UF
//int fa[100005];
//int cnt[100005];
unordered_map<int, int> fa, cnt, rnk;
int components;
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
// components = n;
//}
void Init(int n) {
if (!fa.count(n)) {
fa[n] = n;
cnt[n] = 1;
rnk[n] = 0;
++components;
}
}
int Find(int x) {
int y = x;
while (x != fa[x]) {
x = fa[x];
}
return fa[y] = x;
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x != y) {
if (rnk[x] > rnk[y]) {
fa[y] = x;
cnt[x] += cnt[y];
}
else {
fa[x] = y;
cnt[y] += cnt[x];
if (rnk[x] == rnk[y])
++rnk[y];
}
--components;
}
}
#endif
#ifdef BIG_OP
int o3[105], o1[105]={1}, o2[105]={2};
int l_o3 = 0, l_o1 = 1, l_o2 = 1;
int one[1] = {1};
int big_add(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int carry = 0;
int len = 0;
memset(res, 0, sizeof(int)*(max(l_op2, l_op1)+1));
repi(i,0,max(l_op2, l_op1)) {
int tmp = carry;
if (i<l_op1) {
tmp += op1[i];
}
if (i<l_op2) {
tmp += op2[i];
}
res[len++] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[len++] = carry;
}
return len;
}
int big_mul(int *res, const int *op1, const int *op2, int l_op1, int l_op2) {
int len = l_op1+l_op2-1;
memset(res, 0, sizeof(int)*(len+1));
repi(i,0,l_op1) {
int carry = 0;
repi(j,0,l_op2) {
int tmp = res[i+j] + carry + op1[i] * op2[j];
res[i+j] = tmp%10;
carry = tmp/10;
}
if (carry) {
res[i+l_op2] = carry;
len = max(i + l_op2+1, len);
}
}
return len;
}
int *res = o3, *op1 = o1, *op2 = o2, l_res = l_o3, l_op1 = l_o1, l_op2 = l_o2;
repi(i,1,n) {
l_res = big_mul(res, op1, op2, l_op1, l_op2);
swap(op1, res);
swap(l_op1, l_res);
// peri(t,l_op1-1,0) {
// printf("%d", op1[t]);
// }
// putchar('\n');
l_res = big_add(res, op2, one, l_op2, 1);
swap(op2, res);
swap(l_op2, l_res);
}
#endif
int dfs(int n) {
int res = 0;
int last = sqrt(n);
if (last & 1) {
res = last * (last + 1) >> 1;
} else {
res = last * (last - 1) >> 1;
res += (n - last * last + 1);
}
return res;
}
char str[1005][1005];
int num[1005][1005];
void cnt() {
repi(i,0,n) {
repi(j,0,m) {
if (str[i][j] == '*') {
repi(t,0,8) {
int xx = i+dx[t], yy = j+dy[t];
if (xx < 0 || xx >= n || yy < 0 || yy >= m || str[xx][yy] == '*') {
continue;
}
++num[xx][yy];
}
}
}
}
}
void sweep(int x, int y) {
queue<pii> q;
q.emplace(x,y);
str[x][y] = num[x][y]+'0';
while (!q.empty()) {
auto p = q.front();
q.pop();
if (num[p.x][p.y]) {
continue;
}
repi (i, 0, 8) {
int px = p.x + dx[i];
int py = p.y + dy[i];
if (px >= 0 && px < n && py >= 0 && py < m && str[px][py] == '.') {
q.emplace(px, py);
str[px][py] = num[px][py]+'0';
}
}
}
}
int main() {
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
while (T--)
// while (~scanf("%s", str))
// repi(c,1,T+1)
{
scanf("%d%d", &n, &m);
int x,y;
scanf("%d%d", &x, &y);
--x,--y;
repi(i,0,n) {
scanf("%s", str[i]);
}
if (str[x][y] == '*') {
puts("GG");
} else {
cnt();
sweep(x,y);
repi(i,0,n) {
puts(str[i]);
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif