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不相等，那么就不能简
单的搜索，需要在深搜内部再加入一个条件，保证所有的可能都能够搜到。
#include<bits/stdc++.h>
using namespace std;
const int N=8;
int n=0,ans=0,k=0;
bool col[N];//判断该列是否遍历过
char g[N][N];//存储字符数组
void dfs(int u,int s){
if(s==k){
ans++;
return;
}
for(int i=u;i<n;i++){
for(int j=0;j<n;j++){
if(!col[j]&&g[i][j]=='#'){
col[j]=true;
dfs(i+1,s+1);
col[j]=false;
}
}
}
}
int main(){
while(~scanf("%d %d",&n,&k)){
if(n==-1&&k==-1)break;
ans=0;//初始化，防止上一个案例的答案的影响；
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf(" %c",&g[i][j]);
}
}
dfs(0,0);
printf("%d\n",ans);
}
return 0;
} 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 1 | Sample Output 1 |
|---|---|
1 3 10 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 3 8 5 8 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 1 7 2 6 3 8 4 9 |
1 |
解析：简单的暴搜，每一个可能性都被考虑到，只需要保存其最小值即可。
import java.util.Scanner;
public class Main{
static int n=0,ans=Integer.MAX_VALUE;
static boolean s[]=new boolean [10];
static int h=1,k1=0;
static int a[]=new int[20];//酸度数组
static int b[]=new int[20];//甜度数组
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
for(int i=0;i<n;i++) {
a[i]=cin.nextInt();
b[i]=cin.nextInt();
if(i==0) {
ans=Math.abs(a[i]-b[i]);
}
int l=Math.abs(a[i]-b[i]);
ans=Math.min(ans, l);//找到只有一种调料的最小差
}
if(n==1)System.out.println(ans);
else {
dfs(0);
System.out.println(ans);
}
}
private static void dfs(int u) {
// TODO Auto-generated method stub
if(u==n) {
ans=Math.min(ans,h);
return;
}
for(int i=0;i<n;i++) {
if(!s[i]) {
s[i]=true;
h*=a[i];
k1+=b[i];
//简单的暴搜，每一个可能性都被考虑到，只需要保存其最小值即可
ans=Math.min(ans,Math.abs(h-k1));
dfs(u+1);
h/=a[i];
k1-=b[i];
s[i]=false;
}
}
}
}
C - 全排列
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有 'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入格式
输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在 11 到 66 之间。
输出格式
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：
已知 S = s_1s_2...s_k, T = t_1t_2...t_kS=s1s2...sk,T=t1t2...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
解析：类似全排列问题，只需要每次遍历，记录并标记每次遍历选择的数即可。
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static boolean s[]=new boolean[26];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
char c[]=cin.next().toCharArray();
char g[]=new char[c.length];//记录每次选择的是哪一个
Arrays.sort(c);
dfs(0,c,g);
}
private static void dfs(int u, char[] c,char []g) {
// TODO Auto-generated method stub
if(u==c.length) {
for(int i=0;i<c.length;i++) {
System.out.print(g[i]);
}System.out.println();
return;
}
for(int i=0;i<c.length;i++) {
if(!s[i]) {
s[i]=true;
g[u]=c[i];
dfs(u+1,c,g);
s[i]=false;
}
}
}
}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
解析：为了保证分解的有序进行，在每次深搜时都需要记录上一个加入的值。
import java.util.Scanner;
public class Main{
static int n=0;
static int a[]=new int[30];//用来存储每一次选择的数
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
dfs(1,1,0);
}
private static void dfs(int u,int last,int sum) {
// TODO Auto-generated method stub
if(sum==n) {
System.out.print(n+"=");
for(int i=1;i<u;i++) {
if(i<u-1)System.out.print(a[i]+"+");
else System.out.println(a[i]);
}
return;
}
for(int i=last;i<n;i++) {//每次从上一个的最后一个数开始遍历，保证了不重复
if(sum+i<=n) {
a[u]=i;
dfs(u+1,i,sum+i);
}
}
}
}
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输出后不换行
解析：本题主要考察输出格式和深搜
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner{//用于快速读入大量数据
BufferedReader br;
StringTokenizer st;
public FastScanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in),16384);
eat("");
}
public void eat(String s) {
st = new StringTokenizer(s);
}
public String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
return null;
}
}
public boolean hasNext() {
while(!st.hasMoreTokens()) {
String s = nextLine();
if(s==null) return false;
eat(s);
}
return true;
}
public String next() {
hasNext();
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
static int a[]=new int[20];
static int n=0;
static boolean s[]=new boolean[20];
static FastScanner cin = new FastScanner(System.in);//快读
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//快速输出
public static void main(String[] args) {
int t=0;
while(cin.hasNext()) {
n=cin.nextInt();
t++;
if(t!=1)out.println();
out.println("Case "+t+":");
a[0]=1;
s[1]=true;
dfs(1);
out.flush();
}
}
private static void dfs(int u) {
// TODO Auto-generated method stub
if(u==n) {
if(!check(a[0]+a[n-1]))return;
for(int i=0;i<n;i++) {
if(i!=n-1)out.print(a[i]+" ");
else out.println(a[i]);
}
out.flush();
return;
}
for(int i=2;i<=n;i++) {
if(!s[i]&&check(i+a[u-1])) {
s[i]=true;
a[u]=i;
dfs(u+1);
s[i]=false;
}
}
}
private static boolean check(int m) {//判断是否为素数
// TODO Auto-generated method stub
for(int i=2;i<=m/i;i++) {
if(m%i==0)return false;
}
return true;
}
}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
解析：对每个点进行宽搜，满足条件就加一；然后再从满足条件的数开始搜起，直到整个图形搜索完毕。
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner{//用于快速读入大量数据
BufferedReader br;
StringTokenizer st;
public FastScanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in),16384);
eat("");
}
public void eat(String s) {
st = new StringTokenizer(s);
}
public String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
return null;
}
}
public boolean hasNext() {
while(!st.hasMoreTokens()) {
String s = nextLine();
if(s==null) return false;
eat(s);
}
return true;
}
public String next() {
hasNext();
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
static char g[][]=new char[30][30];//储存字符
static boolean s[][]=new boolean[30][30];//判断该点是否已经被搜过
static int h=0,w=0,x=0,y=0,ans=0;
static int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0};
static FastScanner cin = new FastScanner(System.in);//快读
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//快速输出
public static void main(String[] args) {
while(cin.hasNext()) {
h=cin.nextInt();
w=cin.nextInt();
if(h==0&&w==0)break;
for(int i=0;i<w;i++) {
g[i]=cin.next().toCharArray();
int t=String.valueOf(g[i]).indexOf("@");
if(t!=-1) {
x=i;y=t;//得到起始点的位置
}
}
for(int i=0;i<w;i++) {
Arrays.fill(s[i], false);//初始化，避免上一次判断带来的影响
}
ans=0;
bfs();
System.out.println(ans+1);
}
}
private static void bfs() {
// TODO Auto-generated method stub
Queue<int[]>q=new LinkedList<>();
// System.out.println(x+" "+y);
q.add(new int[] {x,y});
while(!q.isEmpty()) {
int t[]=q.poll();
if(!s[t[0]][t[1]]&&g[t[0]][t[1]]=='.') {
ans++;
// System.out.println(t[0]+" "+t[1]);
}
s[t[0]][t[1]]=true;
for(int i=0;i<4;i++) {
int x1=t[0]+dx[i],y1=t[1]+dy[i];
if(x1>=0&&x1<w&&y1>=0&&y1<h&&!s[x1][y1]&&g[x1][y1]=='.') {
q.add(new int[] {x1,y1});
}
}
}
}
}G - Knight Moves
原题来自：POJ 1915
编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。
输入格式
第一行给出骑士的数量 nn。
在接下来的 3n3n 行中，每 33 行描述了一个骑士。其中，
- 第一行一个整数 LL 表示棋盘的大小，整个棋盘大小为 L\times LL×L；
- 第二行和第三行分别包含一对整数 (x,y)(x,y)，表示骑士的起始点和终点。假设对于每一个骑士，起始点和终点均合理。
输出格式
对每一个骑士，输出一行一个整数表示需要移动的最小步数。如果起始点和终点相同，则输出 00。
样例
| Input | Output |
|---|---|
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。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class node{
int x,y,step;
}
public class Main{
static int N=310;
static boolean s[][]=new boolean[N][N];
static int x=0,y=0,x1=0,y1=0,n;
static int dx[]= {-2,-2,-1,1,2,2,1,-1},dy[]= {-1,1,2,2,1,-1,-2,-2};
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
int t=cin.nextInt();
while(t-->0) {
n=cin.nextInt();
x=cin.nextInt();y=cin.nextInt();
x1=cin.nextInt();y1=cin.nextInt();
for(int i=0;i<=n;i++) {
Arrays.fill(s[i],false);
}
bfs();
}
}
private static void bfs() {
// TODO Auto-generated method stub
Queue<node>q=new LinkedList<>();
node h=new node();
h.x=x;h.y=y;h.step=0;
// System.out.println(h.x+" "+h.y);
q.add(h);
while(!q.isEmpty()) {
node t=q.poll();
if(t.x==x1&&t.y==y1) {
System.out.println(t.step);
return;
}
for(int i=0;i<8;i++) {
int x2=t.x+dx[i],y2=t.y+dy[i];
if(x2>=0&&x2<n&&y2>=0&&y2<n&&!s[x2][y2]) {
node h1=new node();
h1.x=x2;h1.y=y2;h1.step=t.step+1;
// System.out.println(h1.step);
q.add(h1);
s[h1.x][h1.y]=true;
}
}
}
}
}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
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0Sample Output
0
1
2
2
解析：能够进行几次深搜答案就是多少
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int m=0,n=0,ans=0;
static char g[][]=new char[110][110];
static boolean s[][]=new boolean[110][110];
static int dx[]= {0,1,1,1,0,-1,-1,-1},dy[]= {1,1,0,-1,-1,-1,0,1};
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
while(cin.hasNext()) {
m=cin.nextInt();n=cin.nextInt();
if(m==0)break;
ans=0;
for(int i=0;i<m;i++) {
g[i]=cin.next().toCharArray();
Arrays.fill(s[i], false);
}
//双重循环遍历，每次宽搜都把搜过的做上标记，看有几个
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(!s[i][j]&&g[i][j]=='@') {
bfs(i,j);
ans++;
// System.out.println(i+" "+j);
}
}
}
System.out.println(ans);
}
}
private static void bfs(int x, int y) {
// TODO Auto-generated method stub
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {x,y});
s[x][y]=true;
while(!q.isEmpty()) {
int t[]=q.poll();
for(int i=0;i<8;i++) {
int x1=t[0]+dx[i],y1=t[1]+dy[i];
if(x1>=0&&x1<m&&y1>=0&&y1<n&&!s[x1][y1]&&g[x1][y1]=='@') {
s[x1][y1]=true;
q.add(new int[] {x1,y1});
}
}
}
}
}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差不多，换汤不换药
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int m=0,n=0,ans=0;
static char g[][]=new char[110][110];
static boolean s[][]=new boolean[110][110];
static int dx[]= {0,1,1,1,0,-1,-1,-1},dy[]= {1,1,0,-1,-1,-1,0,1};
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
m=cin.nextInt();n=cin.nextInt();
ans=0;
for(int i=0;i<m;i++) {
g[i]=cin.next().toCharArray();
Arrays.fill(s[i], false);
}
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(!s[i][j]&&g[i][j]=='W') {
bfs(i,j);
ans++;
// System.out.println(i+" "+j);
}
}
}
System.out.println(ans);
}
private static void bfs(int x, int y) {
// TODO Auto-generated method stub
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {x,y});
s[x][y]=true;
while(!q.isEmpty()) {
int t[]=q.poll();
for(int i=0;i<8;i++) {
int x1=t[0]+dx[i],y1=t[1]+dy[i];
if(x1>=0&&x1<m&&y1>=0&&y1<n&&!s[x1][y1]&&g[x1][y1]=='W') {
s[x1][y1]=true;
q.add(new int[] {x1,y1});
}
}
}
}
}
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
解析：用数组来存储二叉树，然后递归遍历，简直太妙了，学习我一个大佬同学的，赞~ （要用拿去）
import java.util.Scanner;
public class Main{
static int a[][]=new int[100010][2];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
int n=cin.nextInt();
for(int i=1;i<=n;i++) {
a[i][0]=cin.nextInt();
a[i][1]=cin.nextInt();
}
// System.out.println(a[2][1]);
preorder(1);
}
private static void preorder(int i) {
// TODO Auto-generated method stub
if(i!=0) {
System.out.println(i);
preorder(a[i][0]);
preorder(a[i][1]);
}
}
}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
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int n=0,m=0;
static int sx=0,sy=0,ex=0,ey=0;
static char g[][]=new char[20][20];
static boolean s[][]=new boolean[20][20];
static int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0};
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
m=cin.nextInt();
for(int i=0;i<n;i++) {
g[i]=cin.next().toCharArray();
if(String.valueOf(g[i]).indexOf("S")!=-1) {
sx=i;sy=String.valueOf(g[i]).indexOf("S");
}
if(String.valueOf(g[i]).indexOf("T")!=-1) {
ex=i;ey=String.valueOf(g[i]).indexOf("T");
}
}
if(bfs())System.out.println("yes");
else System.out.println("no");
}
private static boolean bfs() {
// TODO Auto-generated method stub
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {sx,sy});
s[sx][sy]=true;
while(!q.isEmpty()) {
int t[]=q.poll();
if(t[0]==ex&&t[1]==ey) {
return true;
}
// System.out.println(t[0]+" "+t[1]);
for(int i=0;i<4;i++) {
int x=t[0]+dx[i],y=t[1]+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&!s[x][y]&&g[x][y]!='*'&&g[x][y]!='S') {
s[x][y]=true;
q.add(new int[] {x,y});
}
}
}
return false;
}
}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
解析：在每次深搜的时候都记录马已经走过的点数，当点数为格子数时，说明马已经走完了一次了，答案加一。
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int n=0,m=0,x=0,y=0;
static boolean s[][]=new boolean[10][10];
static int dx[]= {-2,-2,-1,1,2,2,1,-1},dy[]= {-1,1,2,2,1,-1,-2,-2};
static int ans=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
int t=cin.nextInt();
while(t-->0) {
n=cin.nextInt();m=cin.nextInt();
x=cin.nextInt();y=cin.nextInt();
ans=0;
for(int i=0;i<10;i++) {
Arrays.fill(s[i], false);
}
s[x][y]=true;
dfs(x,y,1);
System.out.println(ans);
}
}
private static void dfs(int x1, int y1, int sum) {
// TODO Auto-generated method stub
if(sum>=n*m) {
ans++;
return;
}
for(int i=0;i<8;i++) {
int x2=x1+dx[i],y2=y1+dy[i];
if(x2>=0&&x2<n&&y2>=0&&y2<m&&!s[x2][y2]) {
s[x2][y2]=true;
dfs(x2,y2,sum+1);
s[x2][y2]=false;
}
}
}
}