帮人做钓鱼网站以及维护,wordpress手机菜单导航,绍兴市工程建设网站,重要新闻事件题目来源
路径之谜 不愧是国赛的题目
题意
题目中会给你两个数组#xff0c;我这里是分别用row和col来表示 每走一步#xff0c;往左边和上边射一箭#xff0c;走到终点的时候row数组和col数组中的值必须全部等于0这个注意哈#xff0c;看题目看了半天#xff0c;因为…题目来源
路径之谜 不愧是国赛的题目
题意
题目中会给你两个数组我这里是分别用row和col来表示 每走一步往左边和上边射一箭走到终点的时候row数组和col数组中的值必须全部等于0这个注意哈看题目看了半天因为我第一次模拟的时候是只要找到一条到达重点的路径即可
思路
我用dfs来写的模板就不写了就说一下需要注意的点
到终点的时候row和col必须全部等于0起点的时候也要向上面和左边射一箭
代码 dfs
import java.util.*;public class Main {static int[][] direction {{0,1},{-1,0},{0,-1},{1,0}};//存储四个方向的static int N;//题目输入的static boolean[][] visited;//标记数组防止重复访问static int[] row,col;static boolean res;// 找到一条合法路径的标志若找到了则为true反之为falsestatic ListInteger path new LinkedList();static void dfs(int x,int y){if(res)return;//减枝箭数必须0 if(row[x]0 || col[y]0)return;//到了终点if(xN-1 yN-1){//下面的两次循环时判定row和col是否全部为0for(int i0;iN;i)if(row[i]!0)return;for(int i0;iN;i)if(col[i]!0)return;for(Integer num: path)System.out.print(num );System.out.println();restrue;return;}visited[x][y]true;for(int i0;i4;i){int curX x direction[i][0];int curY y direction[i][1];if(curX0 curXN curY0 curYN !visited[curX][curY]){visited[curX][curY] true;row[curX]--;col[curY]--;path.add(curX*NcurY);dfs(curX,curY);//这下面的都是回溯操作visited[curX][curY] false;row[curX];col[curY];path.remove(path.size()-1);}}}public static void main(String[] args) {Scanner s new Scanner(System.in);N s.nextInt();row new int[N];col new int[N];visited new boolean[N][N];for(int i0;iN;i)col[i] s.nextInt();for(int j0;jN;j)row[j] s.nextInt();path.add(0);//0要加上哦// 起点也要向北和向左射一箭row[0]--;col[0]--;dfs(0,0);s.close();}
}代码 bfs
周总结的时候再来尝试一次
