797.所有可能的路径：
class Solution {
List<List<Integer>> ans=new LinkedList<>();
List<Integer> list=new LinkedList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
list.add(0);
backTracking(graph,0);
return ans;
}
private void backTracking(int[][] graph,int x){
if (x==graph.length-1){
ans.add(new LinkedList<>(list));
}
for (int i = 0; i < graph[x].length; i++) {
list.add(graph[x][i]);
backTracking(graph,graph[x][i]);
list.remove(list.size()-1);
}
}
}岛屿数量：
深搜：
class Solution {
int ans=0;
int[] dx={0,1,-1,0};
int[] dy={1,0,0,-1};
public int numIslands(char[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j]=='1'){
ans++;
grid[i][j]='0';
backTracking(grid,i,j);
}
}
}
return ans;
}
private void backTracking(char[][] grid,int x,int y){
for (int i = 0; i < 4; i++) {
int newx=x+dx[i];
int newy=y+dy[i];
if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]=='0')continue;
grid[newx][newy]='0';
backTracking(grid,newx,newy);
}
}
}广搜：
class Solution {
int ans=0;
int[] dx={0,1,-1,0};
int[] dy={1,0,0,-1};
public int numIslands(char[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j]=='1'){
ans++;
bfs(grid,new boolean[grid.length][grid[0].length],i,j);
}
}
}
return ans;
}
private void bfs(char[][] grid,boolean[][] vis,int x,int y) {
Deque<Pair> pairDeque=new LinkedList<>();
pairDeque.push(new Pair(x,y));
while (!pairDeque.isEmpty()){
Pair pair = pairDeque.pop();
int x1 = pair.x;
int y1 = pair.y;
for (int i = 0; i < 4; i++) {
int newx=x1+dx[i];
int newy=y1+dy[i];
if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]=='0'){
continue;
}
grid[newx][newy]='0';
pairDeque.push(new Pair(newx,newy));
}
}
}
class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}岛屿的最大面积：
int max=0;
int[] dx={0,1,-1,0};
int[] dy={1,0,0,-1};
int count=1;
public int maxAreaOfIsland(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j]==1){
count=0;
dfs(grid,i,j);
max=Math.max(max,count);
}
}
}
return max;
}
private void dfs(int[][] grid,int x,int y){
count++;
grid[x][y]=0;
for (int i = 0; i < 4; i++) {
int newx=x+dx[i];
int newy=y+dy[i];
if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
continue;
}
grid[newx][newy]=0;
dfs(grid,newx,newy);
}
}
public static void main(String[] args) {
LeetCode695dfs leetCode695=new LeetCode695dfs();
int max = leetCode695.maxAreaOfIsland(new int[][]{{1}});
System.out.println(max);
}class Solution {
int max=0;
int[] dx={0,1,-1,0};
int[] dy={1,0,0,-1};
int count=1;
public int maxAreaOfIsland(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j]==1){
count=0;
bfs(grid,i,j);
max=Math.max(count,max);
}
}
}
return max;
}
private void bfs(int[][] grid,int x,int y){
Deque<pair> pairDeque=new LinkedList<>();
pairDeque.push(new pair(x,y));
grid[x][y]=0;
while (!pairDeque.isEmpty()){
pair pop = pairDeque.pop();
count++;
int x1 = pop.x;
int y1 = pop.y;
for (int i = 0; i < 4; i++) {
int newx=x1+dx[i];
int newy=y1+dy[i];
if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
continue;
}
grid[newx][newy]=0;
pairDeque.push(new pair(newx,newy));
}
}
}
class pair{
int x;
int y;
public pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}1020：飞地的数量：
class Solution {
int ans=0;
int[] dx={0,1,-1,0};
int[] dy={1,0,0,-1};
boolean flag=true;
public int numEnclaves(int[][] grid) {
for (int i = 0; i < grid[0].length; i++) {
if (grid[0][i]==1){
grid[0][i]=0;
dfs(grid,0,i);
}
if (grid[grid.length-1][i]==1){
grid[grid.length-1][i]=0;
dfs(grid,grid.length-1,i);
}
}
for (int i = 0; i < grid.length; i++) {
if (grid[i][0]==1){
grid[i][0]=0;
dfs(grid,i,0);
}
if (grid[i][grid[0].length-1]==1){
grid[i][grid[0].length-1]=0;
dfs(grid,i,grid[0].length-1);
}
}
for (int i = 1; i < grid.length-1; i++) {
for (int j = 1; j < grid[0].length-1; j++) {
if (grid[i][j]==1) ans++;
}
}
return ans;
}
private void dfs(int[][] grid,int x,int y){
for (int i = 0; i < 4; i++) {
int newx=x+dx[i];
int newy=y+dy[i];
if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
continue;
}
grid[newx][newy]=0;
dfs(grid,newx,newy);
}
}
}这题广搜更胜一筹：
public class LeetCode1020bfs {
int ans=0;
int[] dx={0,1,-1,0};
int[] dy={1,0,0,-1};
public int numEnclaves(int[][] grid) {
for (int i = 0; i < grid[0].length; i++) {
if (grid[0][i]==1){
grid[0][i]=0;
bfs(grid,0,i);
}
if (grid[grid.length-1][i]==1){
grid[grid.length-1][i]=0;
bfs(grid,grid.length-1,i);
}
}
for (int i = 0; i < grid.length; i++) {
if (grid[i][0]==1){
grid[i][0]=0;
bfs(grid,i,0);
}
if (grid[i][grid[0].length-1]==1){
grid[i][grid[0].length-1]=0;
bfs(grid,i,grid[0].length-1);
}
}
for (int i = 1; i < grid.length-1; i++) {
for (int j = 1; j < grid[0].length-1; j++) {
if (grid[i][j]==1) ans++;
}
}
return ans;
}
private void bfs(int[][] grid,int x,int y){
Deque<pair> deque=new LinkedList<>();
deque.push(new pair(x,y));
grid[x][y]=0;
while (!deque.isEmpty()){
pair pop = deque.pop();
int x1 = pop.x;
int y1 = pop.y;
for (int i = 0; i < 4; i++) {
int newx=x1+dx[i];
int newy=y1+dy[i];
if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
continue;
}
grid[newx][newy]=0;
deque.push(new pair(newx,newy));
}
}
}
class pair{
int x;
int y;
public pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
被围绕的区域：
class Solution {
int[] dx={0,1,-1,0};
int[] dy={1,0,0,-1};
public void solve(char[][] board) {
int[][] flag=new int[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
if (board[i][0]=='O'){
dfs(board,i,0,flag);
}
if (board[i][board[0].length-1]=='O'){
dfs(board,i,board[0].length-1,flag);
}
}
for (int i = 0; i < board[0].length; i++) {
if (board[0][i]=='O'){
dfs(board,0,i,flag);
}
if (board[board.length-1][i]=='O'){
dfs(board,board.length-1,i,flag);
}
}
for (int i = 1; i <board.length-1 ; i++) {
for (int j = 1; j < board[0].length-1; j++) {
if (flag[i][j]==0&&board[i][j]=='O'){
board[i][j]='X';
}
}
}
}
private void dfs(char[][] board, int x, int y, int[][] flag) {
flag[x][y]=1;
for (int i = 0; i < 4; i++) {
int newx=x+dx[i];
int newy=y+dy[i];
if (newx<0||newy<0||newx>=board.length||newy>=board[0].length||board[newx][newy]=='X'||flag[newx][newy]==1){
continue;
}
dfs(board,newx,newy,flag);
}
}
}