A - chessboard problem

Put pieces on a chessboard of a given shape (the shape may be irregular), and there is no difference between the pieces. It is required that any two pieces cannot be placed in the same row or column in the chessboard. Please program to solve all feasible placement schemes C for placing k pieces for a chessboard of given shape and size.

Input

The input contains multiple sets of test data.
The first row of each group of data is two positive integers, n k, separated by a space, indicating the chessboard to be described in an n*n matrix and the number of pieces to be placed. n <= 8 , k <= n
When it is - 1 - 1, it indicates the end of input.
The following N lines describe the shape of the chessboard: each line has n characters, where # represents the chessboard area Represents a blank area (the data ensures that there are no redundant blank rows or columns).

Output

For each group of data, a row of output is given, and the number of output schemes C (data guarantee C < 2 ^ 31).

Sample Input

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

Sample Output

2
1

Analysis: this problem is a relatively simple deep search, as long as the search element k layer meets the conditions; Because the question K and n are not equal, then it can't be simplified

For single search, you need to add a condition inside the deep search to ensure that all possibilities can be found.

#include<bits/stdc++.h>
using namespace std;

const int N=8;
int n=0,ans=0,k=0;
bool col[N];//Judge whether the column has been traversed 
char g[N][N];//Store character array 

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;//Initialization to prevent the influence of the answer of the previous case; 
		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

You have ， NN ingredients, and each ingredient has acidity ， SS ， and bitterness ， BB. When these ingredients are used to make Perket, the total acidity is the product of the acidity of all ingredients, and the total bitterness is the sum of the bitterness of all ingredients. You need to add at least one ingredient.

In order to make the taste moderate, the absolute value of the difference between total acidity and bitterness should be as small as possible.

input

The first line contains 11 integers N \ (1\le N\le 10)N (1 ≤ N ≤ 10) - quantity of ingredients.

Next ， NN ， lines ， 22 integers per line ， S_iSi # and # B_iBi - acidity and bitterness of each ingredient. If all ingredients are used to make Perket, the total acidity and bitterness \ le 10^9 ≤ 109.

output

N lines, 1} integers per line - the minimum value.

1
3 10

7

2
3 8
5 8

1

4
1 7
2 6
3 8
4 9

1

Analysis: for a simple burst search, every possibility is considered, and only the minimum value needs to be saved.

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];//Acidity array
	static int b[]=new int[20];//Sweetness array
	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);//Find the minimum difference with only one seasoning
		}
		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];
				//In a simple burst search, every possibility is considered, and only the minimum value needs to be saved
				ans=Math.min(ans,Math.abs(h-k1));
				dfs(u+1);
				h/=a[i];
				k1-=b[i];
				s[i]=false;
			}
		}
	}

}

C - Full Permutation

Given a string composed of different lowercase letters, output all the full permutations of the string. We assume that there is' a '<' B '<... <' for lowercase letters Y '<' Z ', and the letters in the given string have been arranged from small to large.

Input format

The input has only one line, which is a string composed of different lowercase letters. It is known that the length of the string is between {11} and {66}.

Output format

Output all permutations of this string, one permutation per line. The smaller alphabetic order is required to be arranged in the front. The alphabetical order is defined as follows:

S = s_1s_2...s_k, T = t_1t_2...t_kS=s1​s2​... sk​,T=t1​t2​... tk, then ﹤ s < TS < T ﹤ is equivalent to the existence of ﹤ p (1 \le p \le k)p(1 ≤ P ≤ k), such that ﹤ 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 holds.

Sample Input

abc

Sample Output

abc
acb
bac
bca
cab
cba

Analysis: similar to the full permutation problem, you only need to record and mark the number selected for each traversal.

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];//Record which one is selected each time
		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 - natural number splitting

For any natural number {nn} greater than {11}, it can always be divided into the sum of several natural numbers less than {nn}.

Now please write a program to find all the splits of # nn #.

Input format

The input file consists of one line and contains a natural number, i.e. the natural number to be split n(1 \le n \le 20)n(1 ≤ n ≤ 20).

Output format

The output file has several lines, and each line contains an equation, which represents a feasible split (see the example for format and order).

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

Analysis: in order to ensure the orderly decomposition, the last added value needs to be recorded during each deep search.

import java.util.Scanner;

public class Main{
	static int n=0;
	static int a[]=new int[30];//Used to store the number of each selection
	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++) {//Each time, it starts to traverse from the last number of the previous one to ensure no repetition
			if(sum+i<=n) {
				a[u]=i;
				dfs(u+1,i,sum+i);
			}
		}
	}

}

E - Prime Ring Problem

Enter the positive integer n, and arrange the integers 1, 2,..., n into a ring so that the sum of two adjacent integers is prime. When outputting, it is arranged counterclockwise from integer 1. The same ring is output exactly once. If n ≤ 16, there must be a solution.

Multiple groups of data are read in to the end of EOF.

Add a line Case i before group i data output:

Add a blank line between two adjacent sets of outputs.

sample input

6
8

sample output

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

Output format tips

There is no space at the end of the line
Do not wrap after the last Case output

Analysis: this topic mainly investigates the output format and deep search

import java.io.*;
import java.util.*;
public class Main {
	static class FastScanner{//Used to quickly read in large amounts of data
		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);//Read quickly
	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//Fast output
	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) {//Judge whether it is prime
		// 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

There is a rectangular room covered with square tiles. The color of each tile is either red or black. A man stood on a black tile. He can move from one tile to one of the four adjacent tiles. However, he is not allowed to move on the red tiles, he is only allowed to move on the black tiles.

Write a program that allows him to repeat the above movement and judge the number of black tiles he can reach.

input

The input consists of multiple data sets. The starting row of the dataset contains two positive integers W and H; W and H are the number of tiles in the x - and y-directions, respectively. W and H do not exceed 20.

In the dataset, there are H rows, each containing W characters. Each character represents the color of a tile as follows.

'.' - a black tile
'#' - a red tile
'@' - a man, standing on a black tile (just once in a dataset)

The input ends with a line containing two zeros.

output

For each dataset, the program should output a line containing the number of tiles he can reach from the initial tile (including the initial tile itself).

Sample input

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

Sample output

45
59
6
13

Analysis: perform a wide search for each point, and add one if the conditions are met; Then start searching from the number that meets the conditions until the whole graph is searched.

import java.io.*;
import java.util.*;
public class Main {
	static class FastScanner{//Used to quickly read in large amounts of data
		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];//Store character
	static boolean s[][]=new boolean[30][30];//Judge whether the point has been searched
	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);//Read quickly
	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//Fast output
	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;//Get the position of the starting point
				}
			}
			for(int i=0;i<w;i++) {
				Arrays.fill(s[i], false);//Initialization to avoid the impact of the last judgment
			}
			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

The original question comes from: POJ 1915

Write a program to calculate the minimum steps required for a knight to move from one grid on the chessboard to another. The position to which the knight can move in one step is shown in the figure below.

Input format

The first line gives the number of Knights {nn.
In the following {3n3n} lines, each} 33} line describes a knight. Among them,

• The first line is an integer ， ll ， indicating the size of the chessboard. The size of the whole chessboard is ， L\times LL × L；
• The second and third lines contain a pair of integers (x,y)(x,y) respectively, representing the starting and ending points of the knight. Suppose that for each knight, the starting point and ending point are reasonable.

Output format

For each knight, output an integer on a line to represent the minimum number of steps to move. If the start point and the end point are the same, the output is 0.00.

Sample

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0

Data range and tips

For 100 \% 100% data, there are 4\le L\le 3004 ≤ L ≤ 300, ensuring 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

A company is responsible for detecting underground oil layers and dealing with a large rectangular area at a time. First create a grid, divide the land into many square blocks, and then detect each block with sensing equipment to determine whether the block contains oil. A piece of land containing oil is called pocket. If two pocket edges are adjacent or diagonally adjacent, they belong to the same reservoir. Your job is to determine how many different oil layers are in a grid.

Input

The input contains multiple sets of data. Each group of data starts with a row containing m and N, which are the number of rows and columns in the grid (1 < = m < = 100, 1 < = n < = 100), separated by a space. If m = 0, the input ends. Here are m lines, each line has n characters (excluding the end of line characters). Each character corresponds to a piece of land, either "*" for no oil, or "@" for a pocket.

Output

How many different oil layers are there in the output grid.

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0
1
2
2

Analysis: how many deep searches can be carried out? The answer is how many

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);
			}
			
			//Double loop traversal. Mark the searched for each wide search. See how many are there
			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

Due to the recent rainfall, ponds at different locations have been formed in Farmer John's farmland. The farmland is represented as a rectangle, which contains n x m (1 < = n < = 100; 1 < = m < = 100) small squares. Each square contains either water ('W ') or dry land ('. '). Farmer John wanted to find out how many ponds had formed in his farmland. A pond is connected by a square containing water, where a square is regarded as adjacent to all eight surrounding squares.

Give farmer John's farmland data map and judge how many ponds there are in the map.

input

*First line: two integers separated by spaces: N and M

*Section 2 N + 1 line: each line is M characters, representing one line in Farmer John's farmland. Each character is either 'W' or '.'. There is no space between characters.

output

*Line 1: the number of ponds in Farmer John's farmland.

Sample input

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

Sample output

3

Tips

Output details:

There are three ponds: one on the upper left, one on the lower left and one on the right.

Analysis: this question is similar to H. change the soup without changing the dressing

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});
				}
			}
		}
		
	}

}

Preorder traversal of J - binary tree

Enter an integer n (n < = 100000) to represent the number of nodes in the binary tree, numbered 1~n. It is agreed that node 1 is the root node of the binary tree. Then enter n lines, each line includes two integers, and the i line represents the numbers of the left and right child nodes of the node numbered i. If a node has no left child node, the first integer of the corresponding input line is 0; If a node has no right child node, the second integer of the corresponding row is 0.
The binary tree is traversed in sequence and the number of each node is output, and one number is output for each line.

Preorder traversal (DLR) is a kind of binary tree traversal, which is also called root first traversal, preorder traversal and preorder tour. It can be recorded as about the root. Preorder traversal first accesses the root node, then traverses the left subtree, and finally traverses the right subtree.

Input

The first line: an integer n, the next N lines, each line has two integers

Output

Output n lines, one integer per line, representing the node number.

Sample Input

5
2 5
3 4
0 0
0 0
0 0

Sample Output

1
2
3
4
5

Analysis: use an array to store a binary tree, and then recursively traverse it. It's wonderful. Learn from one of my big classmates, like ~ (take it)

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 - maze (I)

One day, Mr. garlic fell into a maze. Mr. garlic wanted to escape. The poor Mr. garlic didn't even know whether there was a way out of the maze.

For the sake of the poor garlic gentleman, please tell the clever garlic gentleman if there is a way to escape.

Input format

On the first line, enter two integers ， nn ， and ， mm to indicate that this is a ， n \times mn × m ， maze.

The next step is to enter a maze of {nn} rows and} mm} columns. Where'S' represents the position of the garlic gentleman, '*' represents the wall, and the garlic gentleman cannot pass through, '.' It means the way, garlic gentleman can pass' Move,'T 'indicates the exit of the maze (garlic king can only move to four adjacent positions - up, down, left and right).

Output format

Output a string. If the garlic gentleman can escape the maze, output "yes", otherwise output "no".

Data range

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 - MA Zori

In Chinese chess, horses move in a Japanese pattern. Please write a program. Given a chessboard of n*m size and the initial position (x, y) of the horse, it is required that the same point on the chessboard cannot be passed repeatedly. Calculate how many ways the horse can traverse all points on the chessboard.

Input

The first line is an integer t (T < 10), indicating the number of test data groups. Each set of test data contains a row of four integers, which are the size of the chessboard and the initial position coordinates n, m, X and y. (0<=x<=n-1,0<=y<=m-1, m < 6, n < 6)

Output

Each group of test data contains a row, which is an integer, indicating the total number of ways that the horse can traverse the chessboard, and 0 means that it cannot traverse once.

Sample Input

1
5 4 0 0

Sample Output

32

Analysis: during each deep search, the number of points the horse has passed is recorded. When the number of points is the grid number, it means that the horse has gone once, and the answer is increased by one.

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;
			}
		}
	}

}