版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434739
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
水题,直接深度优先搜索即可,代码如下:
public class SolutionDay09_P1979 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int W = in.nextInt();
int H = in.nextInt();
char[][] map = new char[H][W];
if (W == 0 && H == 0)
break;
for (int i = 0; i < H; i++) {
char[] ss = in.next().trim().toCharArray();
for (int j = 0; j < W; j++) {
map[i][j] = ss[j];
}
}
System.out.println(solve(map));
}
in.close();
}
private static int solve(char[][] map) {
int row = map.length;
int col = map[0].length;
count = 0;
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (map[i][j] == '@'){
dfs(map, i, j);
}
}
}
return count;
}
static int count = 0;
private static void dfs(char[][] map, int i, int j){
map[i][j] = '#';
int row = map.length;
int col = map[0].length;
count ++;
int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
for (int d = 0; d < 4; d++){
int x = i + directions[d][0];
int y = j + directions[d][1];
if (x >= 0 && x < row && y >= 0 && y < col && map[x][y] == '.'){
dfs(map, x, y);
}
}
}
}
在H * W的矩形果园里有苹果、梨、蜜柑三种果树, 相邻(上下左右)的同种果树属于同一个区域,给出果园的果树分布,求总共有多少个区域。 (原题的样图中苹果为リ,梨为カ,蜜柑为ミ, 图中共10个区域)undefined 输入: 多组数据,每组数据第一行为两个整数H,W(H <= 100, W <= 100), H =0 且 W = 0代表输入结束。以下H行W列表示果园的果树分布, 苹果是@,梨是#, 蜜柑是*。undefined 输出: 对于每组数据,输出其区域的个数。
依旧很水,代码如下:
public class SolutionDay09_A0118 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int W = in.nextInt();
int H = in.nextInt();
char[][] map = new char[H][W];
if (W == 0 && H == 0)
break;
for (int i = 0; i < H; i++) {
char[] ss = in.next().trim().toCharArray();
for (int j = 0; j < W; j++) {
map[i][j] = ss[j];
}
}
System.out.println(solve(map));
}
in.close();
}
private static int solve(char[][] map){
int row = map.length;
int col = map[0].length;
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (map[i][j] != '.'){
count ++;
dfs(map, i, j, map[i][j]);
}
}
}
return count;
}
private static void dfs(char[][] map, int i, int j, char c){
map[i][j] = '.';
int row = map.length;
int col = map[0].length;
int[][] directions = {{-1,0},{1,0},{0,1},{0,-1}};
for (int d = 0; d < 4; d++){
int x = i + directions[d][0];
int y = j + directions[d][1];
if (x >= 0 && x < row && y >= 0 && y < col && map[x][y] == c){
dfs(map, x, y, c);
}
}
}
}
有一个形似央视大楼(Orz)的筒,从A口可以放球,放进去的球可通过挡板DE使其掉进B裤管或C裤管里,现有带1-10标号的球按给定顺序从A口放入,问是否有一种控制挡板的策略可以使B裤管和C裤管中的球从下往上标号递增。undefined 输入: 第一行输入数据组数N。接下来N行为N组具体数据,每组数据中有10个整数,代表球的放入顺序。undefined 输出: 对于每组数据,若策略存在,输出YES;若不存在,输出NOundefined 翻译来自http://blog.csdn.net/synapse7/article/details/14454885
本题有多种解法,dp求最长递减子序列。此处我们用DFS,因为每次最多判断10个球。
思路:
准备两个容器,如果左边容器能放入小球,则继续。否则,尝试放入右边那个容器,如果两个均不能放入小球,那自然而然应该返回”NO”.
鸽巢原理,两个容器中的元素总是满足单调递增,如果出现三个连续的递减元素时,那么两个容器都不能装下第三个元素,因此DFS将直接结束,否则DFS一定能遍历到i>10
的情况。代码如下:
public class SolutionDay09_A0033 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 0; i < n; i++){
for(int j = 1; j <= 10; j++){
ball[j] = in.nextInt();
}
System.out.println(solve(ball));
}
in.close();
}
static int kase;
static int[] ball = new int[15];
static int[] l = new int[15];
static int[] r = new int[15];
private static String solve(int[] ball){
kase = 0;
dfs(1, 1, 1);
return kase == 1 ? "YES" : "NO";
}
private static void dfs(int i, int j, int k){
if (i > 10){ //终止条件
kase = 1;
return;
}
if (kase == 1) return;
if (ball[i] > l[j-1]){ //守卫条件
l[j] = ball[i];
dfs(i+1, j+1, k);
}
if (ball[i] > r[k-1]){ //守卫条件
r[k] = ball[i];
dfs(i+1, j, k+1);
}
}
}
扔石头,上下左右四个方向如果某一个方向紧挨着block就不能扔这个方向,否则碰到block停住,block消失,再次四个方向扔。
思路:
DFS穷尽搜索,从起点开始,向四个方向探索,碰到block时,回到上一步,且删除block。如果不幸,在某个方向后达到终点的步数超过了最小规定的步数,那么剪枝,并且在一步步返回时,进行现场还原,重新让删除的block,变回block,且换个方向继续搜索。代码如下:
public class SolutionDay09_P3009 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int w = in.nextInt();
int h = in.nextInt();
row = h;
col = w;
if (w == 0 && h == 0)
break;
int[][] board = new int[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
board[i][j] = in.nextInt();
}
}
System.out.println(solve(board));
}
in.close();
}
static int row, col;
static int sx, sy;
static int min_step;
static int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
private static int solve(int[][] board) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (2 == board[i][j]) {
sx = i;
sy = j;
// 连环跳,好技巧
i = row;
break;
}
}
}
board[sx][sy] = 0;
min_step = 11;
dfs(sx, sy, 0, board);
return min_step > 10 ? -1 : min_step;
}
private static void dfs(int x, int y, int step, int[][] board) {
// 超过最小步数,进行剪枝
if (step >= 10 || step > min_step) {
return;
}
for (int i = 0; i < 4; i++) {
int nx = x;
int ny = y;
// 让石头往固定的方向一直飞
while (nx >= 0 && nx < row && ny >= 0 && ny < col) {
switch (board[nx][ny]) {
case 0: {
// keep go
nx += directions[i][0];
ny += directions[i][1];
}
break;
case 3: {
//到达终点,记录最小步数
if (step + 1 < min_step) {
min_step = step + 1;
}
//重新换个方向
nx = -1;
}
break;
case 1: {
// 撞到了block
if (!(nx - directions[i][0] == x && ny - directions[i][1] == y)) { //起点下一个撞击方向不能紧挨着block
board[nx][ny] = 0;
dfs(nx - directions[i][0], ny - directions[i][1], step + 1, board);
//还原状态
board[nx][ny] = 1;
}
//重新选择一个方向
nx = -1;
}
break;
default:
break;
}
}
}
}
}
典型的回溯+剪枝算法,得空得强化整理下,这一章节暂告一段落。