原创
题目大意：
钓鱼岛由一个主岛和一些附属岛屿组成，小明决定去钓鱼岛探险。下面这个10*10的二维矩阵就是钓鱼岛
的航拍地图。图中数字表示海拔，0表示海洋，1~9都表示陆地。小明的飞机将会降落在（6,8）处，现在需要
计算出小明将落地所在岛的面积（即有多少个格子）。注意此处把与小明降落点上下左右相链接的陆地视为同
一岛屿。
题意很简单，即给出一个点，求这个点所在的岛屿即可。数字只要不是0，都不用理会大小。
思路很直观，直接BFS。
import java.util.*; public class 宝岛探险 { static int total=0; //统计岛屿面积 static int n; //行 static int m; //列 static int start_x; //初始位置 static int start_y; static int x[]; //队列横坐标 static int y[]; //队列纵坐标 static int maze[][]; static int book[][]; //标记 public static void main(String[] args) { Scanner reader=new Scanner(System.in); n=reader.nextInt(); m=reader.nextInt(); start_x=reader.nextInt(); start_y=reader.nextInt(); maze=new int[n][m]; book=new int[n][m]; x=new int[n*m]; y=new int[n*m]; int dir[][]= { {0,1},{1,0},{0,-1},{-1,0} }; //右、下、左、上 int head=0; int tail=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { maze[i][j]=reader.nextInt(); book[i][j]=0; //数组初始化 } } //初始位置入队列 x[tail]=start_x; y[tail]=start_y; book[start_x][start_y]=1; tail++; total++; while(head<tail) { for(int i=0;i<4;i++) { int dx=x[head]+dir[i][0]; int dy=y[head]+dir[i][1]; if(dx<0 || dx>n-1 || dy<0 || dy>m-1) { //越界判断 continue; } if(maze[dx][dy]==0 || book[dx][dy]==1) { continue; } x[tail]=dx; y[tail]=dy; tail++; book[dx][dy]=1; total++; } head++; //出队列 } System.out.println(total); } }
深度优先搜索也可以，重点是由于每个点只可以统计一次，所以不需要回溯！
import java.util.*; public class 宝岛探险2 { static int total=1; static int n; static int m; static int start_x; static int start_y; static int maze[][]; static int book[][]; static int dir[][]= { {0,1},{1,0},{0,-1},{-1,0} }; //右、下、左、上 static void dfs(int x,int y) { for(int i=0;i<4;i++) { int dx=x+dir[i][0]; int dy=y+dir[i][1]; if(dx<0 || dx>n-1 || dy<0 || dy>m-1) { continue; } if(maze[dx][dy]==0 ||book[dx][dy]==1) { continue; } total++; book[dx][dy]=1; dfs(dx,dy); } } public static void main(String[] args) { Scanner reader=new Scanner(System.in); n=reader.nextInt(); m=reader.nextInt(); start_x=reader.nextInt(); start_y=reader.nextInt(); maze=new int[n][m]; book=new int[n][m]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { maze[i][j]=reader.nextInt(); book[i][j]=0; } } book[start_x][start_y]=1; dfs(start_x,start_y); System.out.println(total); } }
测试用例：
10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
输出：38
11:58:54
2018-07-21