Snap面经题目: 可能路径

0002505492

题目描述:

给一个board(n * n), 然后给一个m,m = 至多能过当前点的次数。返回任意起点的可能的所有路径。即board中每个点走过[1,m]遍。

举例:

input:
12
34
m = 2

output:
1243
124342
124213
……

 

import java.util.*;
public class Solution {
	static int m;
	static int n;
	public static List getPath(int[][] board,int k)
	{
		List res = new ArrayList<>();
		Set set = new HashSet<>();
		if(board == null || board.length == 0 || board[0].length == 0) return res;
		m = board.length;
		n = board[0].length;
		Set unused = new HashSet<>();
		Map usage = new HashMap<>();
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++)
			{
				unused.add(i * n + j);
				usage.put(i * n + j, 0);
			}
		}
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++) DFS(board, i, j, k, unused, usage, set, new ArrayList(), res);
		}
		return res;
	}
	private static void DFS(int[][] board , int i, int j, int k, Set unused, Map usage, Set set, List list, List res)
	{
		if(i < 0 || i >= m || j < 0 || j >=n) return;
		if(usage.get(i * n + j) >= k) return;
		boolean flag = unused.contains(i * n + j);
		if(flag) unused.remove(i * n + j);
		usage.put(i * n + j, usage.get(i * n + j) + 1);
		list.add(board[i][j]);
		if(unused.isEmpty()) addToResult(set, list, res);
		DFS(board, i + 1, j, k, unused, usage, set, list, res);
		DFS(board, i - 1, j, k, unused, usage, set, list, res);
		DFS(board, i, j + 1, k, unused, usage, set, list, res);
		DFS(board, i, j - 1, k, unused, usage, set, list, res);
		if(flag) unused.add(i * n + j);
		usage.put(i * n + j, usage.get(i * n + j) - 1);
		list.remove(list.size() - 1);
		
	}
	private static void addToResult(Set set, List list, List res)
	{
		StringBuilder sb = new StringBuilder();
		for(int i: list) sb.append(i);
		if(!set.contains(sb.toString())){
			res.add(sb.toString());
			set.add(sb.toString());
		}
	}
	public static void main(String[] args)
	{
		int[][] board = {{1,2},{3,4}};
		List ans = getPath(board, 2);
		System.out.println("ans.size() = "+ans.size());
		for(String s: ans) System.out.println(s);
	}
}

329total visits,2visits today