题目描述

《连通块内的格子数》

【连通块内的格子数】 n行m列的迷宫，1表示障碍不能通行，0表示可通行；从(1,1)位置出发，走时只能是“上下左右”相邻的格子移动，并且不能走出地图； 请编程输出包含出发点的连通块内有多少格子。(输入数据保证入口可通行) 【输入样例】 4 5 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1 1 【输出样例】 8 #include using namespace std; int n,m;//n、m<=20 bool visited[21][21]; // 访问标记数组 int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}} ;//方向数组“右下左上” int mp[21][21]; // 地图数组 int cnt = 0; // 格子计数 void dfs(int x,int y){ // 连通块内每个格子只搜索一遍，当所有能走到的格子都搜索过了，递归自动结束。 //递归搜索四个方向 for(int i = 0;i<4;i++){ int nx = x + dir[i][0]; int ny = y + dir[i][1]; if((nx>=1 && nx<=n && ny>=1 && ny<=m)&& !visited[nx][ny] && mp[nx][ny]==0){ visited[nx][ny] = true; cnt++; dfs(nx,ny); } } } int main(){ cin >> n >> m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin >> mp[i][j]; } } visited[1][1] = true; cnt++; dfs(1,1); cout << cnt; return 0; } /* 【输入样例2】 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 【输出样例2】 20 【输入用例3】 3 3 0 0 0 0 0 0 0 0 0 【输出用例3】 9 【输入用例4】 3 4 0 1 1 1 1 1 1 1 1 1 1 1 【输出用例4】 1

输入格式

无

输出格式

（见样例）

样例

输入样例 1

4 5
0 0 0 0 1
1 1 0 0 1
0 1 0 0 1
0 0 1 1 1

输出样例 1

8

输入样例 2

4 5
0 0	0 0	0
0 0	0 0	0
0 0	0 0	0
0 0	0 0	0

输出样例 2

20

输入样例 3

3 3
0 0 0
0 0 0
0 0 0

输出样例 3

9

输入样例 4

3 4
0 1 1 1
1 1 1 1
1 1 1 1

输出样例 4

1