小M最近爱上了扫雷游戏，就是在一个n*m的区域中，有地雷，每一个方格上都有一个数字s，表示在这个方格周围有s颗雷，现在给你一张表明地雷的图，并且指定一个位置点开，请输出点开后的数字情况，若点开的地方的数字为0，则向该方格周围扩展，直到遇到数字或者地图边界为止，若点开的地方为地雷,那么直接输出"GG"。
周围指的是上，左上，左，左下，下，右下，右，右上八个方向。
[编程题]大家来扫雷
- 热度指数：1633 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
- 算法知识视频讲解
输入描述:
第一行有两个数字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..
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <errno.h> #define N 1001 #define OK 1 #define ERROR -1 #define MEM_OVERFLOW -2 #define not ! typedef int Status; // 两维平面的纵横坐标系 typedef struct Coordintate { int x; int y; } Coord; // =============== 循环队列的存储结构表示与实现 =============== typedef Coord QElemType; typedef struct { QElemType* base; int front; int rear; int capacity; } SqQueue; Status InitQueue(SqQueue* Q, int capacity) { if (capacity < 1) { printf("InitQueue ERROR: The capacity %d Must be > 0!", capacity); return ERROR; } if (!(Q->base = (QElemType*) malloc((capacity + 1) * sizeof(QElemType)))) { printf("InitQueue Memory Overflow: %s\n", strerror(errno)); exit(MEM_OVERFLOW); } Q->front = Q->rear = 0; Q->capacity = capacity + 1; return OK; } bool QueueEmpty(SqQueue* Q) { return Q->front == Q->rear; } bool QueueFull(SqQueue* Q) { return (Q->rear + 1) % Q->capacity == Q->front; } size_t QueueLength(SqQueue* Q) { return (Q->rear - Q->front + Q->capacity) % Q->capacity; } Status EnQueue(SqQueue* Q, QElemType e) { if (QueueFull(Q)) { puts("EnQueue ERROR: The queue is full!"); return ERROR; } Q->rear = (Q->rear + 1) % Q->capacity; *(Q->base + Q->rear) = e; return OK; } Status DeQueue(SqQueue* Q, QElemType* ret) { if (QueueEmpty(Q)) { puts("DeQueue ERROR: The queue is empty!"); return ERROR; } Q->front = (Q->front + 1) % Q->capacity; *ret = *(Q->base + Q->front); return OK; } Status DestroyQueue(SqQueue* Q) { free(Q->base); return OK; } // =============== 循环队列的存储结构表示与实现 =============== // =============== The global variable area =============== char board[N][N]; int visited[N][N]; int m, n, sx, sy; // =============== The global variable area =============== // =============== function declaration =============== /** 初始化棋盘 */ void initBoard(void); /** 广度优先搜索算法 */ void breadth_first_search_algorithm(); /** 在电脑屏幕上打印扫雷棋盘 */ void printBoard(void); // =============== function declaration =============== int main(const int argc, const char** argv) { initBoard(); // corner case if (board[sy][sx] == '*') return puts("GG"), 0; // GAME OVER == GG // two solutions breadth_first_search_algorithm(); // depth_first_search_algorithm(); printBoard(); return 0; } void initBoard(void) { int x, y; scanf("%d%d", &m, &n); scanf("%d%d", &sy, &sx); getchar(); for (y = 1; y <= m; ++y) { for (x = 1; x <= n; ++x) scanf("%c", &board[y][x]); getchar(); } memset(visited, 0x0000, sizeof visited); } void breadth_first_search_algorithm(void) { SqQueue Q; InitQueue(&Q, 2000); EnQueue(&Q, (Coord) {.x = sx, .y = sy}); visited[sy][sx] = 1; // mark as visited Coord coord; int x, y, r, c, cnt; while (not QueueEmpty(&Q)) { DeQueue(&Q, &coord); x = coord.x, y = coord.y; cnt = 0; // 当前坐标四周8个方向的**数量 for (r = fmax(1, y - 1); r <= fmin(m, y + 1); ++r) for (c = fmax(1, x - 1); c <= fmin(n, x + 1); ++c) cnt += board[r][c] == '*'; board[y][x] = cnt + 48; if (cnt) continue; for (r = fmax(1, y - 1); r <= fmin(m, y + 1); ++r) for (c = fmax(1, x - 1); c <= fmin(n, x + 1); ++c) { if (visited[r][c]) continue; EnQueue(&Q, (Coord) {.x = c, .y = r}); visited[r][c] = 1; // mark as viisted } } DestroyQueue(&Q); } void printBoard(void) { int x, y; for (y = 1; y <= m; ++y) { for (x = 1; x <= n; ++x) printf("%c", board[y][x]); putchar('\n'); } }
编辑于 2021-07-05 17:22:11
回复(0)
/*
连通图的遍历
*/
#include <bits/stdc++.h>
using namespace std;
#define N 1002
int n, m, x, y;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
char a[N][N];
bool display[N][N], vis[N][N];
void count()
{
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i][j] == '*') {
display[i][j] = true;
for(int k = 0; k < 8; k++) {
if(a[i + dx[k]][j + dy[k]] == '*' || a[i + dx[k]][j + dy[k]] == 0) continue;
if(a[i + dx[k]][j + dy[k]] == '.') {
a[i + dx[k]][j + dy[k]] = '1';
} else {
a[i + dx[k]][j + dy[k]]++;
}
}
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i][j] == '.') {
a[i][j] = '0';
}
}
}
}
void sweep()
{
display[x][y] = true;
if(a[x][y] != '0') return;
queue<pair<int, int>> Q;
Q.push(make_pair(x, y));
vis[x][y] = true;
int i, j;
while(!Q.empty()) {
tie(i, j) = Q.front();
Q.pop();
for(int k = 0; k < 8; k++) {
display[i + dx[k]][j + dy[k]] = true;
if(a[i + dx[k]][j + dy[k]] == '0' && vis[i + dx[k]][j + dy[k]] == false) {
vis[i + dx[k]][j + dy[k]] = true;
Q.push(make_pair(i + dx[k], j + dy[k]));
}
}
}
}
void print()
{
if(a[x][y] == '*') {
printf("GG\n");
return;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(display[i][j]) {
printf("%c", a[i][j]);
} else {
printf(".");
}
}
cout << endl;
}
}
int main()
{
// freopen("input.txt","r",stdin);
int i, j;
cin >> n >> m >> x >> y;
memset(a, 0, sizeof(a));
memset(display, 0, sizeof(display));
memset(vis, 0, sizeof(vis));
for(i = 1; i <= n; i++) {
getchar();
for(j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
count(); // 统计全图各点周围的雷数
sweep(); // 连通图扫描出显示区域
print(); // 输出显示区域
}
编辑于 2019-07-16 20:49:35
回复(2)
#include <bits/stdc++.h>
using namespace std;
char G[1002][1002];
int n,m;
int dir[8][2] = {{0,-1}, {0,1}, {-1,0}, {1,0}, {-1,-1}, {-1,1}, {1,-1}, {1,1}};
struct P{
int x,y;
};
int F(int x, int y){
int cnt = 0;
for(int i=x-1;i<=x+1;i++)
for(int j=y-1;j<=y+1;j++)
if(G[i][j]=='*')
cnt++;
G[x][y] = '0' + cnt;
return cnt;
}
void BFS(int x, int y){
queue<P> q;
q.push(P{x,y});
while(!q.empty()){
P p = q.front();
q.pop();
for(int i=0;i<8;i++){
int xx = p.x + dir[i][0];
int yy = p.y + dir[i][1];
if(xx==0 || xx==n+1 || yy==0 || yy==m+1 || G[xx][yy]!='.')
continue;
int s = F(xx,yy);
if(s==0)
q.push(P{xx,yy});
}
}
return;
}
int main(){
int x,y;
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>G[i][j];
if(G[x][y]=='*')
cout<<"GG"<<endl;
else{
if(F(x,y)==0)
BFS(x,y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout<<G[i][j];
cout<<endl;
}
}
return 0;
}
发表于 2019-11-17 03:52:17
回复(0)
需要注意的是，输出结果时，最好一次输出，否则很容易超时。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
int x=sc.nextInt()-1;
int y=sc.nextInt()-1;
char[][] arr=new char[n][m];
for(int i=0;i<n;i++){
arr[i]=sc.next().toCharArray();
}
if(arr[x][y]=='*') {
System.out.println("GG");
}else {
List<Point> list=new ArrayList<>();
arr[x][y]=getBomb(arr,x,y);
list.add(new Point(x,y));
while(list.size()>0) {
click(arr,list) ;
}
StringBuilder sb=new StringBuilder();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
sb.append(arr[i][j]);
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
sc.close();
}
private static void click(char[][] arr,List<Point> list) {
Point p=list.remove(0);
int x=p.getX();
int y=p.getY();
if(arr[x][y]!='0')
return;
for(int i=x-1;i<=x+1;i++) {
if(i<0||i>=arr.length)
continue;
for(int j=y-1;j<=y+1;j++) {
if(j<0||j>=arr[0].length||(i==x&&j==y))
continue;
if(arr[i][j]=='.') {
arr[i][j]=getBomb(arr,i,j);
list.add(new Point(i,j));
}
}
}
}
private static char getBomb(char[][] arr,int x,int y) {
int count=0;
for(int i=x-1;i<=x+1;i++) {
if(i<0||i>=arr.length)
continue;
for(int j=y-1;j<=y+1;j++) {
if(j<0||j>=arr[0].length)
continue;
if(arr[i][j]=='*') {
count++;
}
}
}
return Character.forDigit(count, 10);
}
}
class Point{
private int x;
private int y;
public Point(int x,int y) {
this.x=x;
this.y=y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
编辑于 2021-03-25 21:15:04
回复(2)
//注意输出换行符号，这题卡得比较紧
//深度优先搜索没法做，只能用广度
//最后，感谢 @神经咩 提供思路
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>
using namespace std;
vector dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
//y轴方向数组
vector dy = { -1, 0, 1, -1, 1, -1, 0, 1 };
//检查当前位置的周围**的总数
int Count(vector> &vec, int x, int y) {
int cnt = 0;
int nx = 0, ny = 0;
for (int i = 0; i < 8; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (vec[nx][ny] == '*') {
cnt++;
}
}
vec[x][y] = cnt + '0';
return cnt;
}
//如果当前位置的**个数为0则向周围搜索，直到遇到超出边界或是遇到数字
void BFS_mineSweeper(vector> &vec, int n, int m, int x, int y) {
queue> que;
que.push(make_pair(x, y));
pair temp;
int cnt = 0;
int nx = 0;
int ny = 0;
//广度优先搜索的目的是查找当前点周围的数是否符合要求，使用队列和迭代比较好理解
while (!que.empty()) {
temp = que.front();
que.pop();
for (int i = 0; i < 8; i++) {
nx = temp.first + dx[i];
ny = temp.second + dy[i];
//如果越界或是不为点号，则继续搜索
if (nx n || ny m || vec[nx][ny] != '.') {
continue;
}
//统计当前点周围**的数量
cnt = Count(vec, nx, ny);
//如果**数量为0则加入待搜索队列
if (cnt == 0) {
que.push(make_pair(nx, ny));
}
}
}
}
void mineSweeping() {
int n, m, x, y;
cin >> n >> m >> x >> y;
//防止Count() 判断时发生越界，对数组vec进行外部一圈填充
vector> vec(n+2, vector(m+2));
//接收数组值，注意测试数据是从1开始的
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> vec[i][j];
}
}
if (vec[x][y] == '*') {
cout << "GG" << endl;
}
else {
//当前位置的**个数是否为0
if (Count(vec, x, y) == 0) {
BFS_mineSweeper(vec, n, m, x, y);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << vec[i][j];
}
cout << endl;
}
}
}
int main(){
mineSweeping();
return 0;
}
编辑于 2020-05-17 09:36:01
回复(0)
//贴一下我杂乱的代码
#include<iostream>
(720)#include<string>
#include<vector>
(721)#include<queue>
using namespace std;
int n, m;
vector<vector<int>> Dir = { { -1, 0 },{ -1, -1 },{ 0, -1 },{ 1, -1 },{ 1, 0 },{ 1, 1 },{ 0, 1 },{ -1, 1 } };
void BFS(int i1, int j1, vector<vector<char>> &v, vector<vector<int>> &Num, vector<vector<bool>> &vis) {
queue<vector<int>> q;
q.push(vector<int>{i1, j1});
int row, col;
int i, j;
while (!q.empty()) {
int count = q.size();
for (int k = 0; k < count; k++) {
vector<int> temp = q.front();
q.pop();
i = temp[0];
j = temp[1];
vis[i][j] = true;
for (int t = 0; t < 8; t++) {
row = i + Dir[t][0];
col = j + Dir[t][1];
//cout << "row = " << row << " col = " << col << endl;
if (row >= 0 && row < n && col >= 0 && col < m) {
//cout << "row = " << row << " col = " << col << endl;
//cout << Num[row][col] << endl;
if (Num[row][col] > 0) {
vis[row][col] = true;
}
else if (Num[row][col] == 0 && !vis[row][col]) {
//cout << "row = " << row << " col = " << col << endl;
vis[row][col] = true;
q.push(vector<int> {row, col});
}
}
}
}
}
}
void GetNum(vector<vector<char>> &v, vector<vector<int>> &Num) {
int row, col;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (v[i][j] != '*') {
int count = 0;
for (int k = 0; k < 8; k++) {
row = Dir[k][0] + i;
col = Dir[k][1] + j;
if (row >= 0 && row < n && col >= 0 && col < m && v[row][col] == '*')
count++;
}
Num[i][j] = count;
}
else {
Num[i][j] = -1;
}
}
}
}
void Show(int row, int col, int num, vector<vector<char>> &v) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == row && j == col) {
cout << num;
}
else {
cout << v[i][j];
}
}
cout << endl;
}
}
void ShowBroad(vector<vector<int>> &Num, vector<vector<bool>> &vis) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (Num[i][j] == -1)
cout << "*";
else if (vis[i][j])
cout << Num[i][j];
else
cout << ".";
}
cout << endl;
}
}
void ShowNum(vector<vector<int>> Num) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << Num[i][j]<< " ";
}
cout << endl;
}
}
int main(void) {
cin >> n >> m;
int row, col;
cin >> row >> col;
char c;
vector<vector<char>> v(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> c;
v[i][j] = c;
}
}
vector<vector<int>> Num(n, vector<int>(m));
GetNum(v, Num);
//ShowNum(Num);
if (v[row - 1][col - 1] == '*') {
cout << "GG" << endl;
return 0;
}
else if (Num[row - 1][col - 1] != 0) {
Show(row - 1, col - 1, Num[row - 1][col - 1], v);
}
else {
vector<vector<bool>> vis(n, vector<bool>(m, false));
BFS(row - 1, col - 1, v, Num, vis);
ShowBroad(Num, vis);
}
//system("pause");
return 0;
}
发表于 2020-05-12 23:22:06
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-11 00:54:41 -
2022-09-07 17:24:39 -
2022-09-02 14:09:48
-
2022-08-30 17:03:01 -
2022-08-27 15:37:34
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
