1、中国象棋
算法分析
bfs
时间复杂度)
Java代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int n = 10;
static int m = 9;
static char[][] g = new char[n][m];
static Pair start;
static Pair end;
static int[][] dist = new int[n][m];
static int[] dx = new int[] {-2,-1,1,2,2,1,-1,-2};
static int[] dy = new int[] {1,2,2,1,-1,-2,-2,-1};
static boolean bfs()
{
for(int i = 0;i < n;i ++) Arrays.fill(dist[i], -1);
Queue<Pair> q = new LinkedList<Pair>();
q.add(start);
dist[start.x][start.y] = 0;
while(!q.isEmpty())
{
Pair t = q.poll();
for(int i = 0;i < 8;i ++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] == '#' || dist[a][b] != -1) continue;
q.add(new Pair(a,b));
dist[a][b] = dist[t.x][t.y] + 1;
}
}
if(dist[end.x][end.y] != -1) return true;
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
for(int i = 0;i < n;i ++)
{
char[] temp = scan.next().toCharArray();
for(int j = 0;j < m;j ++)
{
g[i][j] = temp[j];
if(g[i][j] == 'S') start = new Pair(i,j);
if(g[i][j] == 'T') end = new Pair(i,j);
}
}
if(bfs()) System.out.println("Yes");
else System.out.println("No");
}
}
class Pair
{
int x,y;
Pair(int x,int y)
{
this.x = x;
this.y = y;
}
}
2、踏青
算法分析
flood fill 算法
时间复杂度
Java代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 110;
static int n,m;
static char[][] g = new char[N][N];
static boolean[][] st = new boolean[N][N];
static int[] dx = new int[] {0,-1,0,1};
static int[] dy = new int[] {-1,0,1,0};
static void bfs(Pair start)
{
Queue<Pair> q = new LinkedList<Pair>();
q.add(start);
st[start.x][start.y] = true;
while(!q.isEmpty())
{
Pair t = q.poll();
for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] == '.' || st[a][b]) continue;
q.add(new Pair(a,b));
st[a][b] = true;
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0;i < n;i ++)
{
char[] temp = scan.next().toCharArray();
for(int j = 0;j < m;j ++)
{
g[i][j] = temp[j];
}
}
int cnt = 0;
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < m;j ++)
{
if(g[i][j] == '#' && !st[i][j])
{
bfs(new Pair(i,j));
cnt ++;
}
}
}
System.out.println(cnt);
}
}
class Pair
{
int x,y;
Pair(int x,int y)
{
this.x = x;
this.y = y;
}
}
3、引爆炸弹
算法1
dfs
使用row[] 记录所有行，col[]记录所有列，是否被炸过，遍历炸弹位置，若该位置的该行或者该列都都没炸过，则点着炸弹，并且点着的这个炸弹相关连的其他炸弹也需要跟着点着，该位置的列没有炸过，点燃该列的所有炸弹，该位置的行没有炸过，点燃该行的所有炸弹，因此是一个dfs的过程
时间复杂度
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010;
static int n,m;
static boolean[] row = new boolean[N];
static boolean[] col = new boolean[N];
static char[][] g = new char[N][N];
static void dfs(int x,int y)
{
if(!row[x])
{
row[x] = true;
for(int j = 1;j <= m;j ++)
{
if(g[x][j] == '1' && !col[j])
dfs(x,j);
}
}
if(!col[y])
{
col[y] = true;;
for(int i = 1;i <= n;i ++)
{
if(g[i][y] == '1' && !row[i])
dfs(i,y);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for(int i = 1;i <= n;i ++)
{
char[] temp = br.readLine().toCharArray();
for(int j = 1;j <= m;j ++)
{
g[i][j] = temp[j - 1];
}
}
int cnt = 0;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
if(!row[i] && !col[j] && g[i][j] == '1')
{
cnt ++;
dfs(i,j);
}
}
}
System.out.println(cnt);
}
}
算法2
并查集
每个炸弹通过连炸性，可以关系到某些行和某些列，把这些关系到的行和列归并在一起形成一个集合，点燃这些集合
每一行每一列需要用数字进行标识，列 = 列编号 + n
时间复杂度)
Java 代码
import java.util.Scanner;
public class Main {
static int N = 510;
static int n,m;
static char[][] g = new char[N][N];
static int[] p = new int[N * 2];
static boolean[] st = new boolean[N * 2];
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
char[] temp = scan.next().toCharArray();
for(int j = 1;j <= m;j ++)
{
g[i][j] = temp[j - 1];
}
}
for(int i = 1;i <= n + m;i ++) p[i] = i;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
if(g[i][j] == '1')
{
int a = find(i);
int b = find(j + n);
if(a != b) p[a] = b;
}
}
}
int ans = 0;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
if(g[i][j] == '1')
{
int a = find(i);
if(!st[a])
{
ans ++;
st[a] = true;
}
}
}
}
System.out.println(ans);
}
}
网友评论