正经题解｜入门

【算法分析】

dfs，如果下一个点符合条件则继续递归，直到遍历完所有满足条件的点。

sum  //记录走过的砖块个数
mp[][]  //迷宫
vis[][] //vis[x][y]标记点(x,y)是否已访问
DFS(int x, int y)  //当前正在访问的点是(x,y)
    vis[x][y] = true  //标记点(x,y)已访问
    for 点(x, y)的上下左右点(nx,ny)
        if(nx,ny)没越界&&(nx,ny)未访问&&(nx,ny)不是墙
        sum++; //地板数加1
        DFS(nx, ny) 

【参考代码】

#include <iostream>
using namespace std;

const int N = 30;
int w, h, sx, sy, sum;
char mp[N][N];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  
bool vis[N][N]; 		//vis[x][y] 标记点(x,y)是否已访问

bool check(int x, int y){
	return x >= 1 && x <= h && y >= 1 && y <= w;
}

void dfs(int x, int y){  	//当前正在访问的点是(x,y)
	vis[x][y] = true;      //标记点(x,y)已访问
	for(int i = 0; i < 4; i++){
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if(check(nx, ny) && !vis[nx][ny] && mp[nx][ny] == '.'){
			sum++;
			dfs(nx,ny);    //递归访问点(nx,ny) 
		}
	}
	return;
}

int main() {
	cin >> w >> h;  //先输入列数，再输入行数 
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			cin >> mp[i][j];
			if(mp[i][j] == '@') {
				sx = i;
				sy = j;
			}	
		}
	}
	sum++;
	dfs(sx,sy);
	cout << sum;
	return 0;
}

【时间复杂度】

$O(wh)$

【预计得分】

$100pts$