devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

HENAU 冬令营 搜索专题 （A-L）_输入由多个数据集组成。每个数据集由两个整数h和w组成,由一个空格分隔。 输入以两

作者：小小林熬夜学编程 | 2024-02-16 05:19:47

赞

踩

输入由多个数据集组成。每个数据集由两个整数h和w组成,由一个空格分隔。 输入以两

A - 棋盘问题

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

2
1

解析：本题是一个较为简单的深搜，只要搜素k层满足条件即可；因为本题k和n不相等，那么就不能简

单的搜索，需要在深搜内部再加入一个条件，保证所有的可能都能够搜到。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=8;
  5. int n=0,ans=0,k=0;
  6. bool col[N];//判断该列是否遍历过 
  7. char g[N][N];//存储字符数组 
  8.  
  9. void dfs(int u,int s){
  10. 	if(s==k){
  11. 		ans++;
  12. 		return;
  13. 	}
  14. 	
  15. 	for(int i=u;i<n;i++){
  16. 		for(int j=0;j<n;j++){
  17. 			if(!col[j]&&g[i][j]=='#'){
  18. 				col[j]=true;
  19. 				
  20. 				dfs(i+1,s+1);
  21. 				
  22. 				col[j]=false;
  23. 			}
  24. 		}
  25. 	}
  26. }
  27. int main(){
  28. 	while(~scanf("%d %d",&n,&k)){
  29. 		if(n==-1&&k==-1)break;
  30. 		ans=0;//初始化，防止上一个案例的答案的影响； 
  31. 		for(int i=0;i<n;i++){
  32. 			for(int j=0;j<n;j++){
  33. 				scanf(" %c",&g[i][j]);
  34. 			}
  35. 		}
  36. 		
  37. 		dfs(0,0);
  38. 		printf("%d\n",ans);
  39. 	}
  40. 	return 0;
  41. }

B - Perket

你有 NN 种配料，每种配料有酸度 SS 和苦度 BB 。用这些配料做成Perket时，总的酸度为所有配料酸度的乘积，总的苦度是所有配料苦度的和。你至少需要添加一种配料。

为了使口感适中，总的酸度和苦度之差的绝对值应该尽可能小，求这个最小值。

输入

第一行 11 个整数 N \ (1\le N\le 10)N (1≤N≤10) —— 配料的数量。

接下来 NN 行每行 22 个整数 S_iSi​ 和 B_iBi​ —— 每种配料的酸度和苦度。如果用所有配料来做Perket，总的酸度和苦度都 \le 10^9≤109 。

输出

N行，每行 1 个整数 —— 所求的最小值。

Sample Input 1Sample Output 1
1
3 10

7
Sample Input 2Sample Output 2
2
3 8
5 8

1
Sample Input 3Sample Output 3
4
1 7
2 6
3 8
4 9

1

解析：简单的暴搜，每一个可能性都被考虑到，只需要保存其最小值即可。

  1. import java.util.Scanner;
  2.  
  3. public class Main{
  4. 	static int n=0,ans=Integer.MAX_VALUE;
  5. 	static boolean s[]=new boolean [10];
  6. 	static int h=1,k1=0;
  7. 	static int a[]=new int[20];//酸度数组
  8. 	static int b[]=new int[20];//甜度数组
  9. 	public static void main(String[] args) {
  10. 		// TODO Auto-generated method stub
  11. 		Scanner cin=new Scanner(System.in);
  12. 		n=cin.nextInt();
  13. 		for(int i=0;i<n;i++) {
  14. 			a[i]=cin.nextInt();
  15. 			b[i]=cin.nextInt();
  16. 			if(i==0) {
  17. 				ans=Math.abs(a[i]-b[i]);
  18. 			}
  19. 			int l=Math.abs(a[i]-b[i]);
  20. 			ans=Math.min(ans, l);//找到只有一种调料的最小差
  21. 		}
  22. 		if(n==1)System.out.println(ans);
  23. 		else {
  24. 			dfs(0);
  25. 			System.out.println(ans);
  26. 		}
  27. 		
  28. 	}
  29. 	private static void dfs(int u) {
  30. 		// TODO Auto-generated method stub
  31. 		if(u==n) {
  32. 			ans=Math.min(ans,h);
  33. 			return;
  34. 		}
  35. 		
  36. 		for(int i=0;i<n;i++) {
  37. 			if(!s[i]) {
  38. 				s[i]=true;
  39. 				h*=a[i];
  40. 				k1+=b[i];
  41. 				//简单的暴搜，每一个可能性都被考虑到，只需要保存其最小值即可
  42. 				ans=Math.min(ans,Math.abs(h-k1));
  43. 				dfs(u+1);
  44. 				h/=a[i];
  45. 				k1-=b[i];
  46. 				s[i]=false;
  47. 			}
  48. 		}
  49. 	}
  50.  
  51. }

C - 全排列

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有 'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入格式

输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在 11 到 66 之间。

输出格式

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知 S = s_1s_2...s_k, T = t_1t_2...t_kS=s1​s2​...sk​,T=t1​t2​...tk​，则 S < TS<T 等价于，存在 p (1 \le p \le k)p(1≤p≤k)，使得 s_1 = t_1, s_2 = t_2, ..., s_{p - 1} = t_{p - 1}, s_p < t_ps1​=t1​,s2​=t2​,...,sp−1​=tp−1​,sp​<tp​ 成立。

Sample Input

abc

Sample Output

abc
acb
bac
bca
cab
cba

解析：类似全排列问题，只需要每次遍历，记录并标记每次遍历选择的数即可。

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Main{
  5. 	static boolean s[]=new boolean[26];
  6. 	public static void main(String[] args) {
  7. 		// TODO Auto-generated method stub
  8. 		Scanner cin=new Scanner(System.in);
  9. 		char c[]=cin.next().toCharArray();
  10. 		char g[]=new char[c.length];//记录每次选择的是哪一个
  11. 		Arrays.sort(c);
  12. 		dfs(0,c,g);
  13. 		
  14. 	}
  15. 	private static void dfs(int u, char[] c,char []g) {
  16. 		// TODO Auto-generated method stub
  17. 		
  18. 		if(u==c.length) {
  19. 			for(int i=0;i<c.length;i++) {
  20. 				System.out.print(g[i]);
  21. 			}System.out.println();
  22. 			return;
  23. 		}
  24. 		
  25. 		for(int i=0;i<c.length;i++) {
  26. 			if(!s[i]) {
  27. 				s[i]=true;
  28. 				g[u]=c[i];
  29. 				dfs(u+1,c,g);
  30. 				s[i]=false;
  31. 			}
  32. 		}
  33. 		
  34. 	}
  35.  
  36. }

D - 自然数拆分

对于任意大于 11 的自然数 nn，总是可以拆分成若干个小于 nn 的自然数之和。

现请你编写程序求出 nn 的所有拆分。

输入格式

输入文件共一行，包含一个自然数，即要拆分的自然数 n(1 \le n \le 20)n(1≤n≤20)。

输出格式

输出文件有若干行，每行包含一个等式，即代表一种可行的拆分（格式与顺序参见样例）。

Sample Input

5

Sample Output

5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3

解析：为了保证分解的有序进行，在每次深搜时都需要记录上一个加入的值。

  1. import java.util.Scanner;
  2.  
  3. public class Main{
  4. 	static int n=0;
  5. 	static int a[]=new int[30];//用来存储每一次选择的数
  6. 	public static void main(String[] args) {
  7. 		// TODO Auto-generated method stub
  8. 		Scanner cin=new Scanner(System.in);
  9. 		n=cin.nextInt();
  10. 		dfs(1,1,0);
  11. 	
  12. 	}
  13. 	private static void dfs(int u,int last,int sum) {
  14. 		// TODO Auto-generated method stub
  15. 		if(sum==n) {
  16. 			System.out.print(n+"=");
  17. 			for(int i=1;i<u;i++) {
  18. 				if(i<u-1)System.out.print(a[i]+"+");
  19. 				else System.out.println(a[i]);
  20. 			}
  21. 			
  22. 			return;
  23. 		}
  24. 		
  25. 		for(int i=last;i<n;i++) {//每次从上一个的最后一个数开始遍历，保证了不重复
  26. 			if(sum+i<=n) {
  27. 				a[u]=i;
  28. 				dfs(u+1,i,sum+i);
  29. 			}
  30. 		}
  31. 	}
  32.  
  33. }

E - Prime Ring Problem

输入正整数 n，把整数 1,2,…,n 排成一个环，使得相邻两个整数之和均为素数。输出时，从整数 1 开始逆时针排列。同一个环恰好输出一次。n≤16，保证一定有解。

多组数据，读入到EOF结束。

第 i 组数据输出前加上一行Case i:

相邻两组输出中间加上一个空行。

输入样例

6
8

输出样例

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

输出格式提示

行末无空格
最后一个Case输出后不换行

解析：本题主要考察输出格式和深搜

  1. import java.io.*;
  2. import java.util.*;
  3. public class Main {
  4. 	static class FastScanner{//用于快速读入大量数据
  5. 		BufferedReader br;
  6. 		StringTokenizer st;
  7. 		public FastScanner(InputStream in) {
  8. 			br = new BufferedReader(new InputStreamReader(in),16384);
  9. 			eat("");
  10. 		}
  11. 		public void eat(String s) {
  12. 			st = new StringTokenizer(s);
  13. 		}
  14. 		public String nextLine() {
  15. 			try {
  16. 				return br.readLine();
  17. 			} catch (IOException e) {
  18. 				return null;
  19. 			}
  20. 		}
  21. 		public boolean hasNext() {
  22. 			while(!st.hasMoreTokens()) {
  23. 				String s = nextLine();
  24. 				if(s==null) return false;
  25. 				eat(s);
  26. 			}
  27. 			return true;
  28. 		}
  29. 		public String next() {
  30. 			hasNext();
  31. 			return st.nextToken();
  32. 		}
  33. 		public int nextInt() {
  34. 			return Integer.parseInt(next());
  35. 		}
  36. 	}
  37.  
  38. 	static int a[]=new int[20];
  39. 	static int n=0;
  40. 	static boolean s[]=new boolean[20];
  41. 	static FastScanner cin = new FastScanner(System.in);//快读
  42. 	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//快速输出
  43. 	public static void main(String[] args) {
  44. 		int t=0;
  45. 		while(cin.hasNext()) {
  46. 			n=cin.nextInt();
  47. 			t++;
  48. 			if(t!=1)out.println();
  49. 			out.println("Case "+t+":");
  50. 			a[0]=1;
  51. 			s[1]=true;
  52. 			dfs(1);
  53. 			
  54. 			
  55. 			out.flush();
  56. 		}
  57. 	}
  58. 	private static void dfs(int u) {
  59. 		// TODO Auto-generated method stub
  60. 		if(u==n) {
  61. 			
  62. 			if(!check(a[0]+a[n-1]))return;
  63. 			for(int i=0;i<n;i++) {
  64. 				if(i!=n-1)out.print(a[i]+" ");
  65. 				else out.println(a[i]);
  66. 			}
  67. 			out.flush();
  68. 			return;
  69. 		}
  70. 		
  71. 		for(int i=2;i<=n;i++) {
  72. 			if(!s[i]&&check(i+a[u-1])) {
  73. 				s[i]=true;
  74. 				a[u]=i;
  75. 				dfs(u+1);
  76. 				s[i]=false;
  77. 			}
  78. 		}
  79. 	}
  80. 	private static boolean check(int m) {//判断是否为素数
  81. 		// TODO Auto-generated method stub
  82. 		for(int i=2;i<=m/i;i++) {
  83. 			if(m%i==0)return false;
  84. 		}
  85. 		return true;
  86. 	}
  87.  
  88. }

F - Red and Black

有一个长方形的房间，覆盖了正方形的磁砖。每块磁砖的颜色，要么是红色，要么是黑色。一名男子站在一块黑色的磁砖上。他可以从一块磁砖移至相邻四块磁砖中的某一块。但是，他不允许在红色磁砖上移动，他只允许在黑色磁砖上移动。

编写一个程序，使得他允许重复上述的移动，判断他所能到达的黑色磁砖的数量。

输入

输入由多个数据集组成。数据集的起始行包含了两个正整数 W 和 H；W 和 H 分别是 x- 和 y- 方向的磁砖数量。W 和 H 不超过 20 。

在数据集中，还有 H 行，每行包含了 W 个字符。每个字符按如下方式表示一块磁砖的颜色。

'.' - 一块黑色的磁砖
'#' - 一块红色的磁砖
'@' - 一名男子，站在一块黑色磁砖上 (在一个数据集中，恰好出现一次)

以包含两个 0 的一行，表示输入结束。

输出

对于每个数据集，程序应当输出一行，包含他从初始磁砖所能抵达的磁砖数量 (包括初始磁砖自身)。

示例输入

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

示例输出

45
59
6
13

解析：对每个点进行宽搜，满足条件就加一；然后再从满足条件的数开始搜起，直到整个图形搜索完毕。

  1. import java.io.*;
  2. import java.util.*;
  3. public class Main {
  4. 	static class FastScanner{//用于快速读入大量数据
  5. 		BufferedReader br;
  6. 		StringTokenizer st;
  7. 		public FastScanner(InputStream in) {
  8. 			br = new BufferedReader(new InputStreamReader(in),16384);
  9. 			eat("");
  10. 		}
  11. 		public void eat(String s) {
  12. 			st = new StringTokenizer(s);
  13. 		}
  14. 		public String nextLine() {
  15. 			try {
  16. 				return br.readLine();
  17. 			} catch (IOException e) {
  18. 				return null;
  19. 			}
  20. 		}
  21. 		public boolean hasNext() {
  22. 			while(!st.hasMoreTokens()) {
  23. 				String s = nextLine();
  24. 				if(s==null) return false;
  25. 				eat(s);
  26. 			}
  27. 			return true;
  28. 		}
  29. 		public String next() {
  30. 			hasNext();
  31. 			return st.nextToken();
  32. 		}
  33. 		public int nextInt() {
  34. 			return Integer.parseInt(next());
  35. 		}
  36. 	}
  37.  
  38. 	static char g[][]=new char[30][30];//储存字符
  39. 	static boolean s[][]=new boolean[30][30];//判断该点是否已经被搜过
  40. 	static int h=0,w=0,x=0,y=0,ans=0;
  41. 	static int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0};
  42. 	static FastScanner cin = new FastScanner(System.in);//快读
  43. 	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//快速输出
  44. 	public static void main(String[] args) {
  45. 		while(cin.hasNext()) {
  46. 			h=cin.nextInt();
  47. 			w=cin.nextInt();
  48. 			if(h==0&&w==0)break;
  49. 			
  50. 			for(int i=0;i<w;i++) {
  51. 				g[i]=cin.next().toCharArray();
  52. 				int t=String.valueOf(g[i]).indexOf("@");
  53. 				if(t!=-1) {
  54. 					x=i;y=t;//得到起始点的位置
  55. 				}
  56. 			}
  57. 			for(int i=0;i<w;i++) {
  58. 				Arrays.fill(s[i], false);//初始化，避免上一次判断带来的影响
  59. 			}
  60. 			ans=0;
  61. 			bfs();
  62. 			System.out.println(ans+1);
  63. 		}
  64. 	}
  65. 	private static void bfs() {
  66. 		// TODO Auto-generated method stub
  67. 			Queue<int[]>q=new LinkedList<>();
  68. //			System.out.println(x+" "+y);
  69. 			q.add(new int[] {x,y});
  70. 			
  71. 			while(!q.isEmpty()) {
  72. 				
  73. 				int t[]=q.poll();
  74. 				if(!s[t[0]][t[1]]&&g[t[0]][t[1]]=='.') {
  75. 					ans++;
  76. //					System.out.println(t[0]+" "+t[1]);
  77. 				}
  78. 				
  79. 				s[t[0]][t[1]]=true;
  80. 				
  81. 				for(int i=0;i<4;i++) {
  82. 					int x1=t[0]+dx[i],y1=t[1]+dy[i];
  83. 					
  84. 					if(x1>=0&&x1<w&&y1>=0&&y1<h&&!s[x1][y1]&&g[x1][y1]=='.') {
  85. 						q.add(new int[] {x1,y1});
  86. 					}
  87. 				}
  88. 			}
  89. 	}
  90.  
  91. }

G - Knight Moves

原题来自：POJ 1915

编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。

Picture 1

输入格式

第一行给出骑士的数量 nn。
在接下来的 3n3n 行中，每 33 行描述了一个骑士。其中，

  • 第一行一个整数 LL 表示棋盘的大小，整个棋盘大小为 L\times LL×L；
  • 第二行和第三行分别包含一对整数 (x,y)(x,y)，表示骑士的起始点和终点。假设对于每一个骑士，起始点和终点均合理。

输出格式

对每一个骑士，输出一行一个整数表示需要移动的最小步数。如果起始点和终点相同，则输出 00。

样例

InputOutput
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
 
5
28
0

数据范围与提示

对于 100\%100% 的数据，有 4\le L\le 3004≤L≤300，保证 0\le x,y\le L-10≤x,y≤L−1。

 

  1. import java.util.Arrays;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  4. import java.util.Scanner;
  5.  
  6. class node{
  7. 	int x,y,step;
  8. }
  9. public class Main{
  10. 	static int N=310;
  11. 	
  12. 	static boolean s[][]=new boolean[N][N];
  13. 	static int x=0,y=0,x1=0,y1=0,n;
  14. 	static int dx[]= {-2,-2,-1,1,2,2,1,-1},dy[]= {-1,1,2,2,1,-1,-2,-2};
  15. 	public static void main(String[] args) {
  16. 		// TODO Auto-generated method stub
  17. 		Scanner cin=new Scanner(System.in);
  18. 		int t=cin.nextInt();
  19. 		
  20. 		while(t-->0) {
  21. 			n=cin.nextInt();
  22. 			x=cin.nextInt();y=cin.nextInt();
  23. 			x1=cin.nextInt();y1=cin.nextInt();
  24. 			
  25. 			for(int i=0;i<=n;i++) {
  26. 				Arrays.fill(s[i],false);
  27. 			}
  28. 			bfs();
  29. 		}
  30. 	}
  31. 	private static void bfs() {
  32. 		// TODO Auto-generated method stub
  33. 		Queue<node>q=new LinkedList<>();
  34. 		node h=new node();
  35. 		h.x=x;h.y=y;h.step=0;
  36. //		System.out.println(h.x+" "+h.y);
  37. 		q.add(h);
  38. 		while(!q.isEmpty()) {
  39. 			node t=q.poll();
  40. 			if(t.x==x1&&t.y==y1) {
  41. 				System.out.println(t.step);
  42. 				return;
  43. 			}
  44. 			
  45. 			for(int i=0;i<8;i++) {
  46. 				int x2=t.x+dx[i],y2=t.y+dy[i];
  47. 				
  48. 				if(x2>=0&&x2<n&&y2>=0&&y2<n&&!s[x2][y2]) {
  49. 					node h1=new node();
  50. 					h1.x=x2;h1.y=y2;h1.step=t.step+1;
  51. //					System.out.println(h1.step);
  52. 					q.add(h1);
  53. 					s[h1.x][h1.y]=true;
  54. 				}
  55. 			}
  56. 		}
  57. 	}
  58.  
  59. }

H - Oil Deposits

某公司负责探测地下油层，每次处理一个大的矩形区域。先创建一个网格，将土地划分为许多方形块，然后用传感设备分别探测每个地块，以确定该地块是否含有石油。一块含有石油的土地叫做pocket。如果两个pocket边相邻或对角相邻，则它们属于同一油层的一部分。你的工作是确定在一个网格有多少不同的油层。

Input

输入包含多组数据。每组数据都以包含m和n的一行开始，m和n是网格中行和列的数量（1 <= m <= 100，1 <= n <= 100），由一个空格分隔。如果m = 0，则表示输入结束。下面是m行，每行有n个字符(不包括行尾字符)。每个字符对应一块土地，要么是“*”，代表没有油，要么是“@”，代表一个pocket。

Output

输出网格有多少不同的油层。

Sample Input

  1. 1 1
  2. *
  3. 3 5
  4. *@*@*
  5. **@**
  6. *@*@*
  7. 1 8
  8. @@****@*
  9. 5 5 
  10. ****@
  11. *@@*@
  12. *@**@
  13. @@@*@
  14. @@**@
  15. 0 0

Sample Output

0
1
2
2

解析：能够进行几次深搜答案就是多少

  1. import java.util.Arrays;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  4. import java.util.Scanner;
  5.  
  6. public class Main{
  7. 	static int m=0,n=0,ans=0;
  8. 	static char g[][]=new char[110][110];
  9. 	static boolean s[][]=new boolean[110][110];
  10. 	static int dx[]= {0,1,1,1,0,-1,-1,-1},dy[]= {1,1,0,-1,-1,-1,0,1};
  11. 	public static void main(String[] args) {
  12. 		// TODO Auto-generated method stub
  13. 		Scanner cin=new Scanner(System.in);
  14. 		
  15. 		while(cin.hasNext()) {
  16. 			m=cin.nextInt();n=cin.nextInt();
  17. 			if(m==0)break;
  18. 			
  19. 			ans=0;
  20. 			
  21. 			for(int i=0;i<m;i++) {
  22. 				g[i]=cin.next().toCharArray();
  23. 				Arrays.fill(s[i], false);
  24. 			}
  25. 			
  26. 			//双重循环遍历，每次宽搜都把搜过的做上标记，看有几个
  27. 			for(int i=0;i<m;i++) {
  28. 				for(int j=0;j<n;j++) {
  29. 					if(!s[i][j]&&g[i][j]=='@') {
  30. 						bfs(i,j);
  31. 						ans++;
  32. //						System.out.println(i+" "+j);
  33. 					}
  34. 				}
  35. 			}
  36. 			
  37. 			System.out.println(ans);
  38. 		}
  39. 	}
  40. 	private static void bfs(int x, int y) {
  41. 		// TODO Auto-generated method stub
  42. 		Queue<int[]> q=new LinkedList<>();
  43. 		
  44. 		q.add(new int[] {x,y});
  45. 		s[x][y]=true;
  46. 		
  47. 		while(!q.isEmpty()) {
  48. 			int t[]=q.poll();
  49. 			
  50. 			for(int i=0;i<8;i++) {
  51. 				int x1=t[0]+dx[i],y1=t[1]+dy[i];
  52. 				
  53. 				if(x1>=0&&x1<m&&y1>=0&&y1<n&&!s[x1][y1]&&g[x1][y1]=='@') {
  54. 					
  55. 					s[x1][y1]=true;
  56. 					q.add(new int[] {x1,y1});
  57. 				}
  58. 			}
  59. 		}
  60. 		
  61. 	}
  62.  
  63. }

I - Lake Counting

由于最近的降雨，农夫约翰的农田里形成了不同位置的水塘。农田被表示为一个矩形，它包含了 N x M (1 <= N <= 100; 1 <= M <= 100) 个小方格。每个方格中，要么包含了水 ('W')，要么包含了旱地 ('.')。农夫约翰想要弄清楚，他的农田中形成了多少个水塘。一个水塘是由包含了水的方格连通而成，这里一个方格被视作与周围的全部八个方格相邻。

给出农夫约翰的农田数据图，判断图中有多少个水塘。

输入

* 第一行：两个以空格分隔的整数: N 和 M

* 第 2..N+1 行：每行 M 个字符，表示农夫约翰的农田中的一行。每个字符要么是 'W' 要么是 '.'。字符之间没有空格。

输出

* 第一行：农夫约翰的农田中，水塘的数量。

示例输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

示例输出

3

提示

输出细节：

有 3 个水塘：一个位于左上方，一个位于左下方，还有一个位于右边。

解析：本题同H差不多，换汤不换药

  1. import java.util.Arrays;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  4. import java.util.Scanner;
  5.  
  6. public class Main {
  7. 	static int m=0,n=0,ans=0;
  8. 	static char g[][]=new char[110][110];
  9. 	static boolean s[][]=new boolean[110][110];
  10. 	static int dx[]= {0,1,1,1,0,-1,-1,-1},dy[]= {1,1,0,-1,-1,-1,0,1};
  11. 	public static void main(String[] args) {
  12. 		// TODO Auto-generated method stub
  13. 		Scanner cin=new Scanner(System.in);
  14. 			m=cin.nextInt();n=cin.nextInt();
  15. 			ans=0;
  16. 			
  17. 			for(int i=0;i<m;i++) {
  18. 				g[i]=cin.next().toCharArray();
  19. 				Arrays.fill(s[i], false);
  20. 			}
  21. 			
  22. 			
  23. 			for(int i=0;i<m;i++) {
  24. 				for(int j=0;j<n;j++) {
  25. 					if(!s[i][j]&&g[i][j]=='W') {
  26. 						bfs(i,j);
  27. 						ans++;
  28. //						System.out.println(i+" "+j);
  29. 					}
  30. 				}
  31. 			}
  32. 			
  33. 			System.out.println(ans);
  34. 	}
  35. 	private static void bfs(int x, int y) {
  36. 		// TODO Auto-generated method stub
  37. 		Queue<int[]> q=new LinkedList<>();
  38. 		
  39. 		q.add(new int[] {x,y});
  40. 		s[x][y]=true;
  41. 		
  42. 		while(!q.isEmpty()) {
  43. 			int t[]=q.poll();
  44. 			
  45. 			for(int i=0;i<8;i++) {
  46. 				int x1=t[0]+dx[i],y1=t[1]+dy[i];
  47. 				
  48. 				if(x1>=0&&x1<m&&y1>=0&&y1<n&&!s[x1][y1]&&g[x1][y1]=='W') {
  49. 					
  50. 					s[x1][y1]=true;
  51. 					q.add(new int[] {x1,y1});
  52. 				}
  53. 			}
  54. 		}
  55. 		
  56. 	}
  57.  
  58. }

J - 二叉树先序遍历

输入一个整数n（n <= 100000），表示二叉树中节点个数，编号为1~n。约定1号节点为二叉树的根节点。然后输入n行，每行包括两个整数，第i行表示编号为i的节点的左子节点和右子节点的编号。如果某个节点没有左子节点，那么对应输行的第一个整数为0；如果某个节点没有右子节点，那么对应行的第二个整数为0。
先序遍历输出此二叉树每个节点的编号，每行输出一个编号。

先序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、前序遍历、前序周游，可记做根左右。前序遍历首先访问根节点然后遍历左子树，最后遍历右子树。

Input

第一行：一个整数n 接下来n行，每行有两个整数

Output

输出n行，每行一个整数，表示节点编号。

Sample Input

5
2 5
3 4
0 0
0 0
0 0

Sample Output

1
2
3
4
5

解析：用数组来存储二叉树，然后递归遍历，简直太妙了，学习我一个大佬同学的，赞~ （要用拿去）

  1. import java.util.Scanner;
  2.  
  3. public class Main{
  4. 	static int a[][]=new int[100010][2];
  5. 	public static void main(String[] args) {
  6. 		// TODO Auto-generated method stub
  7. 		Scanner cin=new Scanner(System.in);
  8. 		int n=cin.nextInt();
  9. 		for(int i=1;i<=n;i++) {
  10. 			a[i][0]=cin.nextInt();
  11. 			a[i][1]=cin.nextInt();
  12. 		}
  13. //		System.out.println(a[2][1]);
  14. 		preorder(1);
  15. 	}
  16. 	private static void preorder(int i) {
  17. 		// TODO Auto-generated method stub
  18. 		if(i!=0) {
  19. 			System.out.println(i);
  20. 			preorder(a[i][0]);
  21. 			preorder(a[i][1]);
  22. 		}
  23. 	}
  24.  
  25. }

K - 迷宫（一）

一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。

看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。

输入格式

第一行输入两个整数 nn 和 mm，表示这是一个 n \times mn×m 的迷宫。

接下来的输入一个 nn 行 mm 列的迷宫。其中 'S' 表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。

输出格式

输出一个字符串，如果蒜头君可以逃出迷宫输出"yes"，否则输出"no"。

数据范围

1 \le n, m \le 101≤n,m≤10。

Sample Input

3 4
S**.
..*.
***T

Sample Output

no

Sample Input 2

3 4
S**.
....
***T

Sample Output 2

yes
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Scanner;
  4.  
  5. public class Main {
  6. 	static int n=0,m=0;
  7. 	static int sx=0,sy=0,ex=0,ey=0;
  8. 	static char g[][]=new char[20][20];
  9. 	static boolean s[][]=new boolean[20][20];
  10. 	static int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0};
  11. 	
  12. 	public static void main(String[] args) {
  13. 		// TODO Auto-generated method stub
  14. 		Scanner cin=new Scanner(System.in);
  15. 		n=cin.nextInt();
  16. 		m=cin.nextInt();
  17. 		
  18. 		for(int i=0;i<n;i++) {
  19. 			g[i]=cin.next().toCharArray();
  20. 			
  21. 			if(String.valueOf(g[i]).indexOf("S")!=-1) {
  22. 				sx=i;sy=String.valueOf(g[i]).indexOf("S");
  23. 			}
  24. 			if(String.valueOf(g[i]).indexOf("T")!=-1) {
  25. 				ex=i;ey=String.valueOf(g[i]).indexOf("T");
  26. 			}
  27. 		}
  28. 		
  29. 		if(bfs())System.out.println("yes");
  30. 		else System.out.println("no");
  31. 	}
  32. 	private static boolean bfs() {
  33. 		// TODO Auto-generated method stub
  34. 		Queue<int[]> q=new LinkedList<>();
  35. 		
  36. 		q.add(new int[] {sx,sy});
  37. 		s[sx][sy]=true;
  38. 		
  39. 		while(!q.isEmpty()) {
  40. 			int t[]=q.poll();
  41. 			
  42. 			if(t[0]==ex&&t[1]==ey) {
  43. 				return true;
  44. 			}
  45. //			System.out.println(t[0]+" "+t[1]);
  46. 			for(int i=0;i<4;i++) {
  47. 				int x=t[0]+dx[i],y=t[1]+dy[i];
  48. 				
  49. 				if(x>=0&&x<n&&y>=0&&y<m&&!s[x][y]&&g[x][y]!='*'&&g[x][y]!='S') {
  50. 					s[x][y]=true;
  51. 					q.add(new int[] {x,y});
  52. 				}
  53. 			}
  54. 		}
  55. 		return false;
  56. 	}
  57.  
  58. }

L - 马走日

马在中国象棋以日字形规则移动。请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

Input

第一行为整数T(T < 10)，表示测试数据组数。每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 6, n < 6)

Output

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

Sample Input

1
5 4 0 0

Sample Output

32

解析：在每次深搜的时候都记录马已经走过的点数，当点数为格子数时，说明马已经走完了一次了，答案加一。

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Main{
  5. 	static int n=0,m=0,x=0,y=0;
  6. 	static boolean s[][]=new boolean[10][10];
  7. 	static int dx[]= {-2,-2,-1,1,2,2,1,-1},dy[]= {-1,1,2,2,1,-1,-2,-2};
  8. 	static int ans=0;
  9. 	public static void main(String[] args) {
  10. 		// TODO Auto-generated method stub
  11. 		Scanner cin=new Scanner(System.in);
  12. 		int t=cin.nextInt();
  13. 		while(t-->0) {
  14. 			n=cin.nextInt();m=cin.nextInt();
  15. 			x=cin.nextInt();y=cin.nextInt();
  16. 			ans=0;
  17. 			
  18. 			for(int i=0;i<10;i++) {
  19. 				Arrays.fill(s[i], false);
  20. 			}
  21. 			s[x][y]=true;
  22. 			dfs(x,y,1);
  23. 			
  24. 			
  25. 			System.out.println(ans);
  26. 		}
  27. 	}
  28. 	private static void dfs(int x1, int y1, int sum) {
  29. 		// TODO Auto-generated method stub
  30. 		if(sum>=n*m) {
  31. 			ans++;
  32. 			return;
  33. 		}
  34. 		
  35. 		for(int i=0;i<8;i++) {
  36. 			int x2=x1+dx[i],y2=y1+dy[i];
  37. 			if(x2>=0&&x2<n&&y2>=0&&y2<m&&!s[x2][y2]) {
  38. 				s[x2][y2]=true;
  39. 				dfs(x2,y2,sum+1);
  40. 				s[x2][y2]=false;
  41. 			}
  42. 		}
  43. 	}
  44.  
  45. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/91027
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号