首页 > 试题广场 >

大家来扫雷

[编程题]大家来扫雷
  • 热度指数:1542 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

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..
#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)