有没有帮人做机械设计的网站,网站入口百度,有趣的网站游戏,手机怎样建个人网站题干#xff1a;
求每个*能够到达的格子数量#xff0c;只有.可以走#xff08;四个方向扩展#xff09;#xff0c;结果mod 10#xff0c;替换 * 后输出。
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 1000) — the number of rows and co…题干
求每个*能够到达的格子数量只有.可以走四个方向扩展结果mod 10替换 * 后输出。
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the field.
Each of the next n lines contains m symbols: . for empty cells, * for impassable cells.
Output
Print the answer as a matrix as described above. See the examples to precise the format of the output.
Examples
Input
3 3
*.*
.*.
*.*Output
3.3
.5.
3.3Input
4 5
**..*
..***
.*.*.
*.*.*Output
46..3
..732
.6.4.
5.4.3Note
In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).
解题报告 直接对每个.进行搜索看连通块然后对每一个*直接求答案就行了注意不要算重复所以需要set去判重。因为有可能四个方向属于同一个联通块所以不判重就会加四次
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 1000 5;
char maze[MAX][MAX];
int ans[MAX][MAX];
bool vis[MAX][MAX];
int f[MAX*MAX];
int num[MAX*MAX];
int n,m;
int nx[4] {0,1,0,-1};
int ny[4] {1,0,-1,0};
int getf(int v) {return v f[v] ? v : f[v] getf(f[v]);
}
void merge(int u,int v) {int t1 getf(u);int t2 getf(v);f[t2] t1;
}
int get(int x,int y) {return (x-1)*m y;
}
void go(int x,int y) {for(int k 0; k4; k) {int tx x nx[k];int ty y ny[k];if(tx 1 || tx n || ty 1 || ty m) continue;if(maze[tx][ty] * || vis[tx][ty]) continue;merge(get(x,y),get(tx,ty));vis[tx][ty] 1;go(tx,ty);}
}
int main()
{cinnm;for(int i 0; in*m; i) {f[i] i;}for(int i 1; in; i) {scanf(%s,maze[i]1);}for(int i 1; in; i) {for(int j 1; jm; j) {if(maze[i][j] . vis[i][j] 0) {vis[i][j] 1;//别忘这步虽然这题不会WA但是不写是错的。go(i,j);} }}for(int i 1; in; i) {for(int j 1; jm; j) {if(maze[i][j] *) continue;num[getf(get(i,j))];}}for(int i 1; in; i) {for(int j 1; jm; j) {if(maze[i][j] .) ans[i][j] .;else {int cnt 0;setint ss;for(int k 0; k4; k) {int tx i nx[k];int ty j ny[k];if(maze[tx][ty] *)continue;if(tx 1 || tx n || ty 1 || ty m) continue;ss.insert(getf(get(tx,ty)));}auto it ss.begin();for(;it!ss.end();it) cnt num[*it];ans[i][j] cnt;}}}for(int i 1; in; i) {for(int j 1; jm; j) {if(maze[i][j] .) printf(.);else printf(%d,(ans[i][j]1)%10);}puts();}return 0 ;
}
