最后更新
三刷
15-Jan-2017
好熟悉的题了，DFS做，注意比如1-3是经过2的，如果2被访问过，那么1-3也是可以的。
public class Solution {
public int numberOfPatterns(int m, int n) {
int[][] path = new int[10][10];
boolean[] visited = new boolean[10];
/*
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
*/
path[1][3] = path[3][1] = 2;
path[1][7] = path[7][1] = 4;
path[3][9] = path[9][3] = 6;
path[9][7] = path[7][9] = 8;
path[1][9] = path[9][1] = 5;
path[2][8] = path[8][2] = 5;
path[3][7] = path[7][3] = 5;
path[4][6] = path[6][4] = 5;
int res = 0;
for (int i = m; i <= n; i++) {
res += 4 * dfs(i - 1, path, visited, 1);
res += 4 * dfs(i - 1, path, visited, 2);
res += dfs(i - 1, path, visited, 5);
}
return res;
}
public int dfs(int left, int[][] path, boolean[] visited, int pos) {
if (left == 0) {
return 1;
} else {
visited[pos] = true;
int res = 0;
for (int i = 1; i <= 9; i++) {
if (visited[i]) continue;
if (path[i][pos] == 0 || visited[path[i][pos]]) {
res += dfs(left-1, path, visited, i);
}
}
visited[pos] = false;
return res;
}
}
}
这个题我真是做得想打人了卧槽。
题目不难，就是算组合，但是因为是3乘3的键盘，所以只需要从1和2分别开始DFS，结果乘以4，再加上5开始的DFS就行了。
问题是这个傻逼题目的设定是，从1到8不需要经过4或者5。。。
我TEST CASE 2,2 卡了好久好久，做得我怀疑人生了，怎么算都是
(3+5)*4 + 8。。结果答案愣是56.
最后发现题设里从1-8是不需要经过4或者5的，真是要报警了。
public class Solution
{
int res = 0;
public int numberOfPatterns(int m, int n)
{
boolean[][] visited = new boolean[3][3];
visited[0][0] = true;
helper(0,0,m,n,1,visited);
//System.out.println(res);
visited = new boolean[3][3];
visited[0][1] = true;
helper(0,1,m,n,1,visited);
//System.out.println(res);
res *= 4;
visited = new boolean[3][3];
visited[1][1] = true;
helper(1,1,m,n,1,visited);
return res;
}
public void helper(int m, int n, int x, int y, int c, boolean[][] visited)
{
if(c >= x && c <= y) res++;
for(int i = 0; i < 3;i++)
for(int j = 0; j < 3; j++)
{
if(jumpable(visited,m,n,i,j))
{
visited[i][j] = true;
helper(i,j,x,y,c+1,visited);
visited[i][j] = false;
}
}
}
public boolean jumpable(boolean[][] visited, int m1, int n1, int m2, int n2)
{
if(visited[m2][n2]) return false;
int x = Math.abs(m1-m2);
int y = Math.abs(n1-n2);
// adjacent
if(x <= 1 && y <= 1) return true;
// di
if(x == 2 && y == 2) return visited[1][1];
// horizontal
if(x == 0 && y == 2) return visited[m1][1];
// vertical
if(x == 2 && y == 0) return visited[1][n1];
/*
if(x == 1 && y == 2) return visited[m1][1] && visited[m2][1];
if(x == 2 && y == 1) return visited[1][n1] && visited[1][n2];
*/
return true;
}
}
二刷。
08-Nov-2016
这个题光记得一刷的时候颇有怨念，因为跳马子格不算碰到中间2个，卡了好久
（https://discuss.leetcode.com/topic/63038/how-many-people-thought-from-1-to-8-should-visit-voth-4-and-5）
还是以 1 2 5分别作为起点，然后1 和 2的要最后乘以4，因为1-9个数字可以转90°转3次。
这次换了个做法，直接标记所有路径，反正也不是很多。
Time: O(n!)
Space: O(n^2)
public class Solution {
public int numberOfPatterns(int m, int n) {
int[][] path = new int[10][10];
/*
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
*/
path[1][3] = path[3][1] = 2;
path[1][7] = path[7][1] = 4;
path[3][9] = path[9][3] = 6;
path[9][7] = path[7][9] = 8;
path[1][9] = path[9][1] = 5;
path[2][8] = path[8][2] = 5;
path[3][7] = path[7][3] = 5;
path[4][6] = path[6][4] = 5;
int res = 0;
boolean[] visited = new boolean[10];
for (int i = m; i <= n; i++) {
res += 4 * dfs(path, visited, 1, i - 1);
res += 4 * dfs(path, visited, 2, i - 1);
res += dfs(path, visited, 5, i - 1);
}
return res;
}
public int dfs(int[][] path, boolean[] visited, int cur, int left) {
if (left == 0) {
return 1;
} else {
int res = 0;
visited[cur] = true;
for (int i = 1; i <= 9; i++) {
if (visited[i]) continue;
if (path[cur][i] == 0 || visited[path[cur][i]]) {
res += dfs(path, visited, i, left - 1);
}
}
visited[cur] = false;
return res;
}
}
}
一刷的办法通过坐标来判断是否经过，也不错……思考起来稍微麻烦点，实际上正解应该是一刷那种不使用N^2空间。