关注
//棋盘问题
public class Main {
static int REScount = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int[][] arr = new int[n][m];
for(int i=0;i<k;i++){
int x = sc.nextInt();
int y = sc.nextInt();
arr[x][y] = 1;
}
HashSet<String> set = new HashSet<>();
int startX = 0;
int stattY = 0;
int endX = n-1;
int endY = m-1;
process(0,arr,set,startX,stattY,endX,endY);
if(REScount == Integer.MAX_VALUE){
System.out.println(0);
}else{
System.out.println(REScount);
}
}
//
public static void process(int count,int[][] arr,HashSet<String> set,int startX,int startY,int endX,int endY){
if(startX == endX && startY == endY){//到达终点
REScount = Math.min(count, REScount);
return;
}else if( startX<0 || startX>=arr.length || startY<0 || startY>=arr[0].length){//越界
return ;
}else if(arr[startX][startY] ==1){//障碍物不能走
return;
}else {
String loc = startX+"+"+startY;
if(set.contains(loc)){//已经走过
return ;
}else{
set.add(loc);//添加次点
//上下左右走
process(count+1,arr,set,startX-1,startY,endX,endY);
process(count+1,arr,set,startX+1,startY,endX,endY);
process(count+1,arr,set,startX,startY-1,endX,endY);
process(count+1,arr,set,startX,startY+1,endX,endY);
set.remove(loc);//移除改点
}
}
}
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
731027次浏览 11739人参与
# 非技术岗是怎么找实习的 #
74763次浏览 1400人参与
# 海康威视求职进展汇总 #
91659次浏览 1094人参与
# 浅聊一下我实习的辛苦费 #
81637次浏览 763人参与
# 如何写一份好简历 #
263301次浏览 3966人参与
# 硬件人求职现状 #
185177次浏览 2709人参与
# 通信硬件人笔面经互助 #
111993次浏览 2263人参与
# 面试等了一周没回复,还有戏吗 #
40634次浏览 500人参与
# 机械制造面试记录 #
37654次浏览 505人参与
# 24届营销人拿到了几个offer #
4247次浏览 62人参与
# 铜五铁六真的存在吗? #
28344次浏览 298人参与
# 实习生应该准时下班吗 #
76900次浏览 571人参与
# 打工人的辛酸 #
8628次浏览 134人参与
# 运营人的第一份offer应该如何选 #
35331次浏览 643人参与
# 美的求职进展汇总 #
39028次浏览 419人参与
# 如何看待offer收割机的行为 #
224241次浏览 3256人参与
# 产品实习,你更倾向大公司or小公司 #
36502次浏览 560人参与
# 数据人offer决赛圈怎么选 #
44838次浏览 728人参与
# 实习与准备秋招该如何平衡 #
172077次浏览 3115人参与
# 通信硬件薪资爆料 #
201084次浏览 1824人参与