输入包括n+1行:
第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
接下来的n行:
每行m个0或者1,以空格分隔
如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一
4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1
[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
#include <iostream> #include <vector> using namespace std; int Maze[10][10]; #define VISITED 2 int m, n, P; int Dir[4][2] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } }; int Cost[4] = { -1, -1, -3, 0 }; int H = -200; struct MazePoint { MazePoint(int _x, int _y) :x(_x), y(_y) { } int x, y; }; vector<MazePoint> PathStack; vector<MazePoint> MinCostPath; void PushPoint(int x, int y) { PathStack.push_back(MazePoint(x, y)); } void PopPoint() { PathStack.pop_back(); } void PrintPath(const vector<MazePoint>& Path) { for (int i = 0; i < Path.size(); ++i) { cout << "[" << Path[i].x << "," << Path[i].y << "]"; if (i < Path.size() - 1) { cout << ","; } } } void Search(int x, int y, int currP) { PushPoint(x, y); Maze[x][y] = VISITED; if (x == 0 && y == m-1 && currP >= 0) { if (currP > H) { H = currP; MinCostPath = PathStack; } PopPoint(); Maze[x][y] = 1; return; } if(currP > 0) { for (int i = 0; i < 4; ++i) { int nx = x + Dir[i][0]; int ny = y + Dir[i][1]; int nP = currP + Cost[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && Maze[nx][ny] == 1) { Search(nx, ny, nP); } } } PopPoint(); Maze[x][y] = 1; } int main() { cin >> n >> m >> P; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> Maze[i][j]; } } Search(0, 0, P); if (H != -200) { PrintPath(MinCostPath); } else { cout << "Can not escape!"; } return 0; }
n, m, p = [int(x) for x in input().split()] mat0 = [] for _ in range(n): mat0.append([int(x) for x in input().split()]) mat1 = [[None for j in range(m)] for i in range(n)] mat1[0][0] = [0, 0, p] # mat1保存到达[x, y]的前一个点和到达[x, y]剩余的p route = [[0, 0]] steps = [[1, 0], [-1, 0], [0, 1], [0, -1]] flag = True #其实遍历到0,m-1点就可以停止了 while route and flag: x0, y0 = route.pop(0) for step in steps: x1, y1 = x0 + step[0], y0 + step[1] if 0 <= x1 < n and 0 <= y1 < m and mat0[x1][y1] and mat1[x1][y1] is None: if step[0] == -1: new_p = mat1[x0][y0][2] - 3 elif step[0] == 0: new_p = mat1[x0][y0][2] - 1 else: new_p = mat1[x0][y0][2] mat1[x1][y1] = [x0, y0, new_p] route.append([x1, y1]) if x1==0 and y1==m-1: flag = False break if mat1[0][m-1][2] < 0: print('Can not escape!') else: res = [] x, y = 0, m-1 while [x, y] != [0, 0]: res.append([x, y]) x, y = mat1[x][y][0], mat1[x][y][1] res.append([0, 0]) print(','.join(['[{},{}]'.format(x[0], x[1]) for x in res[::-1]]))
//DFS深度搜索,tmp保存路径 #include<iostream> #include<utility> #include<vector> using namespace std; int dp[10][10]; int n,m; int mymax=0; vector<pair<int,int> > res; void myfind(vector<pair<int,int> >& tmp,int x,int y,int p) { if(p<0) return; tmp.push_back(make_pair(x,y)); dp[x][y]=0; //标记已经走过,防止走回头路 if(x==0&&y==m-1) { if(p>=mymax) { mymax=p; res=tmp; } tmp.pop_back(); return; } if(y+1<m&&dp[x][y+1]==1) myfind(tmp,x,y+1, p-1); if(x+1<n&&dp[x+1][y]==1) myfind(tmp,x+1,y, p); if(x-1>=0&&dp[x-1][y]==1) myfind(tmp,x-1,y, p-3); if(y-1>=0&&dp[x][y-1]==1) myfind(tmp,x,y-1, p-1); tmp.pop_back(); dp[x][y]=1; //返回上层时,别忘记恢复 } int main() { int p; while(cin>>n>>m>>p) { for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin>>dp[i][j]; vector<pair<int,int> > tmp; myfind(tmp,0,0,p); if(res.size()==0) cout<<"Can not escape!"<<endl; else { int k; for(k=0;k<res.size()-1;++k) cout<<"["<<res[k].first<<","<<res[k].second<<"]"<<","; cout<<"["<<res[k].first<<","<<res[k].second<<"]"<<endl; } } }
回溯算法,标准流程 import java.util.*; public class Main{ public static void main(String[] args){ Scanner input=new Scanner(System.in); while(input.hasNext()){ int n=input.nextInt(); int m=input.nextInt(); int P=input.nextInt(); int[][] a=new int[n][m]; for(int i=0; i<n; i++) for(int j=0; j<m; j++) a[i][j]=input.nextInt(); boolean[][] flag=new boolean[n][m]; ArrayList<Integer> path=new ArrayList<>(); if(isTruePath(0,0,P,a,path,flag)){ for(int i=0; i<path.size()-2; i+=2) System.out.print("["+path.get(i)+","+path.get(i+1)+"]"+","); System.out.println("["+path.get(path.size()-2)+","+path.get(path.size()-1)+"]"); }else{ System.out.println("Can not escape!"); } } } public static boolean isTruePath(int i, int j, int P, int[][] a, ArrayList<Integer> path, boolean[][] flag){ if(i<0 || i>=a.length || j<0 || j>=a[0].length || P<0 || a[i][j]==0|| flag[i][j]==true) return false; flag[i][j]=true; path.add(i); path.add(j); if(i==0 && j==a[0].length-1){ return true; } if(isTruePath(i,j-1,P-1,a,path,flag)|| isTruePath(i,j+1,P-1,a,path,flag)|| isTruePath(i-1,j,P-3,a,path,flag)|| isTruePath(i+1,j,P,a,path,flag)) return true; path.remove(path.size()-1); path.remove(path.size()-1); return false; } }
上下我的代码,想法就是dfs了~ import java.util.Scanner; /** * Created by Olive on 2017/9/14. */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { // n*m迷宫,小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1) // 小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向 // 上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值 int n = in.nextInt(); int m = in.nextInt(); // 剩余体力值 int power = in.nextInt(); int[][] maze = new int[n][m]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++) maze[i][j] = in.nextInt(); } System.out.println(pathOut(n , m, maze, power)); } } static String path = ""; public static String pathOut(int n, int m, int[][] maze, int power){ if(n <= 0) return "Can not escape!"; boolean[][] visited = new boolean[n][m]; findPath(n, m, maze, 0, 0, "", visited, power); return path; } public static void findPath(int n, int m, int[][] maze, int nowx, int nowy, String res, boolean[][] visited, int power){ if(nowx == 0 && nowy == m - 1 && maze[0][m - 1] == 1){ if(power >= 0) path = res + "[0," + (m - 1) + "]"; else path = "Can not escape!"; return; } if(nowx < n && nowy < m && nowx >= 0 && nowy >= 0 && maze[nowx][nowy] == 1 && !visited[nowx][nowy]){ visited[nowx][nowy] = true; res += "[" + nowx + "," + nowy + "],"; // 水平向右 findPath(n, m, maze, nowx, nowy + 1, res, visited, power - 1); // 向下 findPath(n, m, maze, nowx + 1, nowy, res, visited, power); // 水平向左 findPath(n, m, maze, nowx, nowy - 1, res, visited, power - 1); // 向上 findPath(n, m, maze, nowx - 1, nowy, res, visited, power - 3); } } }
import java.util.Iterator; import java.util.LinkedList; import java.util.Scanner; public class Main { private static int m = 0, n = 0, minCost = Integer.MAX_VALUE, p = 0; private static LinkedList<Point> linkedList = new LinkedList<>(); private static String path = ""; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); p = in.nextInt(); int[][] map = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { map[i][j] = in.nextInt(); } } generate(map, 0, 0, 0); if (minCost == Integer.MAX_VALUE) { System.out.println("Can not escape!"); } else { System.out.println(path.substring(0,path.length()-1)); } } private static void generate(int[][] map, int x, int y, int currentCost) { if (currentCost > p) return; map[x][y] = 2; linkedList.offer(new Point(x, y)); if (x == 0 && y == m - 1) { if (currentCost < minCost){ minCost = currentCost; savePath(); } map[x][y] = 1; linkedList.removeLast(); return; } if (x < n - 1 && map[x + 1][y] == 1) {//down generate(map, x + 1, y, currentCost); } if (x > 0 && map[x - 1][y] == 1) {//up generate(map, x - 1, y, currentCost + 3); } if (y < m - 1 && map[x][y + 1] == 1) {//right generate(map, x, y + 1, currentCost + 1); } if (y > 0 && map[x][y - 1] == 1) {//left generate(map, x, y - 1, currentCost + 1); } map[x][y] = 1; linkedList.removeLast(); } private static void savePath() { Iterator<Point> iterator = linkedList.iterator(); StringBuilder sb = new StringBuilder(); while (iterator.hasNext()) { Point point = iterator.next(); sb.append("[").append(point.x).append(",").append(point.y).append("],"); } path = sb.toString(); } private static class Point { int x = 0; int y = 0; Point(int x, int y) { this.x = x; this.y = y; } } }
#include <stdio.h> #include <iostream> #include <queue> using namespace std; struct Position { int row; int col; }; int main(){ //n行,m列 int n,m; //体力 int health; scanf("%d %d %d",&n,&m,&health); //迷宫的大小 int** grid = new int*[n+2]; for(int i = 0;i<n+2;++i) grid[i] = new int[m+2]; for(int i = 0;i<n+2;++i){ grid[i][0] = grid[i][m+1] = 0;//左边和右边添加障碍物 } for(int i = 0;i<m+2;++i){ grid[0][i] = grid[n+1][i] = 0;//上边和下边添加障碍物 } //接收数据 for(int j = 1;j<n+1;++j) for(int i = 1;i<m+1;++i) scanf("%d",&grid[j][i]); //算法 Position offset[4]; offset[0].row = 0;offset[0].col = 1; offset[1].row = 1;offset[1].col = 0; offset[2].row = 0;offset[2].col = -1; offset[3].row = -1;offset[3].col = 0; Position here; here.col = here.row = 1;//起点 Position finish;//终点 finish.row = 1; finish.col = m; grid[here.row][here.col] = 2; int numbers = 4;//四个方向 //对可到达的位置做标记 queue<Position> q; Position nbr; do { //给相邻位置做标记 for (int i = 0;i<numbers;++i) { //检查相邻位置 nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if(grid[nbr.row][nbr.col] == 1){ //对不可标记的nbr做标记 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if((nbr.row == finish.row) && (nbr.col == finish.col)) break; //把后者插入队列 q.push(nbr); } } //是否到达终点 if((nbr.row == finish.row) && (nbr.col == finish.col)) break; //终点不可到达,可以移到nbr么 if(q.empty()){ cout<<"Can not escape!"; return 0; } here = q.front(); q.pop(); } while (true); //构造路径 int pathLength = grid[finish.row][finish.col] - 2; Position* path = new Position[pathLength]; //从终点回溯 here = finish; for (int j = pathLength - 1;j>=0;--j) { path[j] = here; //寻找最合适的祖先位置,往下扣3滴血,左右扣1滴血,往上不扣血 if(grid[here.row-1][here.col] == j+2){//往上走 health = health; here.row = here.row - 1; } else if(grid[here.row][here.col+1] == j+2){//往左走 health -= 1; here.col = here.col+1; } else if(grid[here.row][here.col-1] == j+2){//往右走 health -= 1; here.col = here.col-1; } else//往下走 { health -= 3; here.row = here.row + 1; } if(health < 0){ cout<<"Can not escape!"; return 0; } } //输出路径 cout<<"["<<0<<","<<0<<"]"<<","; for (int i = 0;i<pathLength-1;++i) { cout<<"["<<path[i].row-1<<","<<path[i].col-1<<"]"<<","; } cout<<"["<<0<<","<<m-1<<"]"; return 0; }
#include <iostream> #include <vector> #include <limits.h> using namespace std; int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int n, m, k; int board[10][10]; bool visited[10][10]; int res = INT_MAX, tempRes = 0; vector<vector<int>> path; vector<vector<int>> temp; void dfs(int i, int j){ if(i == 0 && j == m - 1){ temp.push_back({i, j}); if(tempRes < res){ path = temp; res = tempRes; } temp.pop_back(); return; } if(visited[i][j] == true || board[i][j] == 0){ return; } visited[i][j] = true; temp.push_back({i, j}); for(int idx = 0; idx < 4; idx++){ int newI = i + dirs[idx][0]; int newJ = j + dirs[idx][1]; if(newI >= 0 && newI < n && newJ >= 0 && newJ < m){ if(idx == 0){ tempRes += 3; dfs(newI, newJ); tempRes -= 3; } else if(idx == 2 || idx == 3){ tempRes += 1; dfs(newI, newJ); tempRes -= 1; } else{ dfs(newI, newJ); } } } visited[i][j] = false; temp.pop_back(); } int main(){ cin >> n >> m >> k; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> board[i][j]; } } dfs(0, 0); if(res <= k){ for(int i = 0; i < path.size() - 1; i++){ cout << "[" << path[i][0] << "," << path[i][1] << "],"; } cout << "[" << path.back()[0] << "," << path.back()[1] << "]" << endl; } else{ cout << "Can not escape!" << endl; } return 0; }
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> #include <string.h> typedef struct Position { int row; int col; }Pos; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //栈创建 typedef Pos STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }Stack; void StackInit(Stack* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity = 4; ps->top = 0;//初始给0,top指向栈顶元素的下一个; } void StackDestory(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } //入栈 void StackPush(Stack* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(Stack* ps) { assert(ps); assert(ps->top > 0);//栈空了,直接终止报错 ps->top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top > 0);//栈空了,直接终止报错 return ps->a[ps->top - 1]; } int StackSize(Stack* ps) { assert(ps); return ps->top; } bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //迷宫主程序 Stack path; Stack minpath; //判断是否有通路 bool IsPass(int** Maze, int N, int M, Pos next) { if (next.col >= 0 && next.col < M && next.row >= 0 && next.row < N && Maze[next.row][next.col] == 1) return true; else return false; } //深拷贝 void StackCopy(Stack* dest, Stack* source) { dest->a = (STDataType*)malloc(sizeof(STDataType) * source->capacity); memcpy(dest->a, source->a, sizeof(STDataType) * source->top); dest->capacity = source->capacity; dest->top = source->top; } //判断是否有到终点的路 void GetMazePath(int** Maze, int N, int M, Pos cur, int P) { StackPush(&path, cur); //判断是否到出口 if (cur.col == M - 1 && cur.row == 0 && P>= 0)//到达出口必须要有充足体力 { if (StackEmpty(&minpath) || StackSize(&path) < StackSize(&minpath))//要么minpath为空,要么path比minpath要小 { //深拷贝 StackDestory(&minpath); StackCopy(&minpath, &path); } } Pos next; //将走过的地方置2,防止重走 Maze[cur.row][cur.col] = 2; //探测上下左右四个方向 //上 next = cur; next.row -= 1; if (IsPass(Maze, N, M, next)) { //如果有通路将继续递归 GetMazePath(Maze, N, M, next, P-3); } //下 next = cur; next.row += 1; if (IsPass(Maze, N, M, next)) { GetMazePath(Maze, N, M, next, P); } //左 next = cur; next.col -= 1; if (IsPass(Maze, N, M, next)) { GetMazePath(Maze, N, M, next,P-1); } //右 next = cur; next.col += 1; if (IsPass(Maze, N, M, next)) { GetMazePath(Maze, N, M, next,P-1); } //回溯的过程中将走过的路程重新恢复 Maze[cur.row][cur.col] = 1; //当走到思路,将走错的坐标删除 StackPop(&path); } //采用栈储存路径 //由于先进后出,栈顶为出口,栈底为入口,需要反过来 //所以再创建一个栈将数据倒过来再输出 void PrintPath(Stack* ps) { Stack rPath; StackInit(&rPath); while (!StackEmpty(ps)) { StackPush(&rPath, StackTop(ps)); StackPop(ps); } while (StackSize(&rPath)>1) { Pos top = StackTop(&rPath); printf("[%d,%d],", top.row, top.col); StackPop(&rPath); } //最后一个输出后边没有“,”,所以单独拎出来输出 Pos top = StackTop(&rPath); printf("[%d,%d]\n", top.row, top.col); StackPop(&rPath); StackDestory(&rPath); } int main() { int N = 0, M = 0, P = 0; while (scanf("%d%d%d", &N, &M, &P) != EOF) { //创建迷宫 //先创建行坐标 //由于是二位数组,先创建一个含有N个数组指针的指针数组,指针数组储存的是指针,所以指向这个指针数组的指针为二级指针 //指针数组中每个指针都为数组指针,每个数组指针指向的数组为每一行 int** Maze = (int**)malloc(sizeof(int*) * N); for (int i = 0; i < N; i++) { //Maze[i]就是int*,是一个指针,开辟的空间储存int Maze[i] = (int*)malloc(sizeof(int) * M); } //输入迷宫 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &Maze[i][j]); } } //初始化栈 StackInit(&path); StackInit(&minpath); //定起点 Pos entry = { 0,0 }; GetMazePath(Maze, N, M, entry, P); if (!StackEmpty(&minpath)) { PrintPath(&minpath); } else { printf("Can not escape!\n"); } StackDestory(&minpath); StackDestory(&path); for (int i = 0; i < N; i++) { free(Maze[i]); } free(Maze); Maze = NULL; } return 0; }
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> gpath; int max_life = -1; void dfs(vector<vector<int>> &g, vector<vector<int>> &visited, int x, int y, int life, vector<pair<int, int>> &path) { if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size() || g[x][y] == 0 ||visited[x][y] || life < 0) { return; } path.push_back(make_pair(x, y)); if (x == 0 && y == g[0].size() - 1) { if (life > max_life) { gpath = path; max_life = life; } path.pop_back(); return; } visited[x][y] = 1; dfs(g, visited, x + 1, y, life, path); dfs(g, visited, x - 1, y, life - 3, path); dfs(g, visited, x, y + 1, life - 1, path); dfs(g, visited, x, y - 1, life - 1, path); path.pop_back(); visited[x][y] = 0; } void show_path(vector<pair<int, int>> &path) { for (int i = 0; i < path.size(); ++i) { cout << '[' << path[i].first << ',' << path[i].second << ']'; if (i < path.size() - 1) { cout << ','; } } } int main() { int n, m, life; cin >> n >> m >> life; vector<vector<int>> grids(n, vector<int>(m)); vector<pair<int, int>> path; vector<vector<int>> visited(n, vector<int>(m, 0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> grids[i][j]; } } dfs(grids, visited, 0, 0, life, path); if (!gpath.empty()) { show_path(gpath); } else { cout << "Can not escape!" << endl; } return 0; }
'''引用@rober 大佬的框架改写如下'''n,m,p = [int(x) for x in input().split()] def dfs(grid,visited,path,i,j,p): path.append([i,j]) if i == 0 and j == m - 1: return visited[i][j] = True if i-1>=0 and grid[i-1][j] and visited[i-1][j]==0 and p>=0: dfs(grid,visited,path,i-1,j,p) if j-1>=0 and grid[i][j-1] and visited[i][j-1]==0 and p-1>=0: dfs(grid,visited,path,i,j-1,p-1) if j+1=0: dfs(grid,visited,path,i,j+1,p-1) if i+1=0: dfs(grid,visited,path,i+1,j,p-3) if path[-1][0]==0 and path[-1][1]==m-1: return path.pop() grid = [] for i in range(n): grid.append([int(x) for x in input().split()]) visited = [[False for i in range(m)] for i in range(n)] path = [] dfs(grid,visited,path,0,0,p) if path and path[-1][0]==0 and path[-1][1]==m-1: res = '' for i in path: res += '['+str(i[0])+','+str(i[1])+']'+',' print(res[:-1]) else: print('Can not escape!')
利用优先队列的bfs。节点设置一个step属性,记录的是走到这个位置所需的最少体力,以这个属性在优先队列中排序。其他处理和普通的宽度遍历一样,下面上代码
package 校招真题2017; import java.util.PriorityQueue; import java.util.Scanner; import java.util.Stack; public class 地下迷宫2 { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int m=scan.nextInt(); int p=scan.nextInt(); int[][] map=new int[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ map[i][j]=scan.nextInt(); } } boolean[][] seen=new boolean[n][m]; PriorityQueue queue=new PriorityQueue(); queue.add(new Node(0,0,0,null)); while(!queue.isEmpty()){ Node tmp=queue.poll(); int row=tmp.row; int col=tmp.col; if(seen[row][col]){ continue; }else{ seen[row][col]=true; } if(row==0&&col==m-1){ if(tmp.step>p){ System.out.println("Can not escape!"); return; } Node current=tmp; Stack stack=new Stack(); while(current!=null){ stack.add(current); current=current.prev; } while(stack.size()!=1){ Node nn=stack.pop(); System.out.print("["+nn.row+","+nn.col+"],"); } Node nn=stack.pop(); System.out.print("["+nn.row+","+nn.col+"]"); } //down if(row+1<n&&map[row+1][col]==1){ queue.add(new Node(row+1,col,tmp.step,tmp)); } //up if(row-1>=0&&map[row-1][col]==1){ queue.add(new Node(row-1,col,tmp.step+3,tmp)); } if(col+1<m&&map[row][col+1]==1){ queue.add(new Node(row,col+1,tmp.step+1,tmp)); } if(col-1>=0&&map[row][col-1]==1){ queue.add(new Node(row,col-1,tmp.step+1,tmp)); } } } public static class Node implements Comparable{ int row; int col; int step; Node prev; public Node(int row, int col, int step,Node prev) { this.row = row; this.col = col; this.step = step; this.prev=prev; } public int compareTo(Node o) { if(this.step>o.step){ return 1; }else if(this.step<o.step){ return -1; }else{ return 0; } } } }
//优先往右,上,下,左顺序,往上时要判断移动到的位置是否是上一步走过的位置 //不可避免的情况是,往右是个死胡同,所以如果依靠往左折回去,要恢复其重复的体力 #include <iostream> #include <vector> using namespace std; struct Point{ Point(int a, int b){ x = a; y = b; }; int x; int y; }; int main() { //读入数据 int n,m,p; cin >> n >> m >> p; int ** data = new int*[n]; for(int i = 0; i < m; i++) data[i] = new int[m]; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> data[i][j]; vector<Point> pt; pt.push_back(Point(0,0)); while(p > 0) { if(pt[pt.size() - 1].x == 0 && pt[pt.size() - 1].y == m-1)//如果走到出口,退出 break; int len = pt.size(); if(pt[len-1].y + 1 < m && data[pt[len-1].x][pt[len-1].y + 1])//往右 { pt.push_back(Point(pt[len-1].x, pt[len-1].y + 1)); p -= 1; continue; } if(pt[len-1].x - 1 >= 0 && data[pt[len-1].x - 1][pt[len-1].y])//往上 { if(!(len-2 >= 0 && pt[len-1].x - 1 == pt[len-2].x && pt[len-1].y == pt[len-2].y))//移动的位置与上上个位置不能相同 { pt.push_back(Point(pt[len-1].x - 1, pt[len-1].y)); p -= 3; continue; } } if(pt[len-1].x + 1 < n && data[pt[len-1].x + 1][pt[len-1].y])//往下 { pt.push_back(Point(pt[len-1].x + 1, pt[len-1].y)); continue; } if(pt[len-1].y - 1 >= 0 && data[pt[len-1].x][pt[len-1].y - 1])//往左 { pt.push_back(Point(pt[len-1].x, pt[len-1].y - 1)); p -= 1; continue; } } //没体力或者没到最到出口 if(p < 0 || !(pt[pt.size() - 1].x == 0 && pt[pt.size() - 1].y == m-1)) { cout << "Can not escape!" << endl; return 0; } for(int i = 0; i < pt.size(); i++) { cout << "[" << pt[i].x << "," << pt[i].y << "]"; if(i != pt.size() - 1) cout << ","; } return 0; }
import java.util.ArrayList; import java.util.Scanner; /* * 1 0 0 1 * 1 1 0 1 * 0 1 1 1 * 0 0 1 1 * * [0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3] */ public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int p = sc.nextInt(); int [][] arr = new int[n][m]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) arr[i][j] = sc.nextInt(); //x、y设为起点 int x=0,y=0; //用两个list,放走过的坐标 ArrayList<Integer> xlist = new ArrayList<>(); ArrayList<Integer> ylist = new ArrayList<>(); int i=0; if(fun(x,y,n,m,p,xlist,ylist,arr)) { while(true) { if(i<xlist.size()) System.out.print("["+xlist.get(i)+","+ylist.get(i)+"]"); else break; i++; if(i<xlist.size()) System.out.print(","); } }else System.out.println("Can not escape!"); } private static boolean fun(int x, int y, int n, int m, int p, ArrayList<Integer> xlist, ArrayList<Integer> ylist, int[][] arr) { if(x<0||x>=n||y<0||y>=m||arr[x][y]!=1||p<0) return false; //走过的坐标,赋为-1 arr[x][y] = -1; xlist.add(x); ylist.add(y); if(x==0&&y==m-1) return true; //贪心策略 if(!fun(x-1,y,n,m,p,xlist,ylist,arr)) if(!fun(x,y+1,n,m,p-1,xlist,ylist,arr)) if(!fun(x+1,y,n,m,p-3,xlist,ylist,arr)) if(!fun(x,y-1,n,m,p-1,xlist,ylist,arr)) { //回溯回退,对应坐标赋为0,并且从list中移除 arr[x][y] = 0; xlist.remove(xlist.size()-1); ylist.remove(ylist.size()-1); return false; } else { return true; } else { return true; } else { return true; } else return true; } }
# -*- coding: utf8 -*- def isValid(matrix,n,m,p,x,y,visited): isvisit=(x*m+y in visited) #是否访问 isvalid=(0<=x<n and 0<=y<m) and matrix[x][y]==1#是否通路 hasp=(p>=0)#是否有剩余能量值 return not isvisit and isvalid and hasp #是否可走 def getPath(matrix, n, m, p, x, y, visited, path): if (x, y) == (0, m - 1): return True else: nextpos=[(x,y+1,p-1),(x-1,y,p-3),(x,y-1,p-1),(x+1,y,p)] #向右,向上,向左,向下 (贪心思想,尽可能以最小的消耗靠近终点--右上角 for nextx,nexty,nextp in nextpos: if isValid(matrix,n,m,nextp,nextx,nexty,visited): path.append([nextx,nexty]) visited.add(nextx * m + nexty) if getPath(matrix, n, m, nextp,nextx,nexty, visited, path): return True path.pop(-1) visited.remove(nextx * m + nexty) return False if __name__ == "__main__": n, m, p = map(int, raw_input().split(' ')) matrix = [] for i in range(n): matrix.append(map(int, raw_input().split(' '))) visited = set() path = [[0, 0]] if getPath(matrix, n, m, p, 0, 0, visited, path): print ','.join(map(str, path)).replace(' ', '') else: print "Can not escape!"
#include<iostream> #include<queue> #include<vector> #include<string> using namespace std; void ShowPath(const vector<pair<int, int>>& path){ int len=path.size(); for(int i=0; i<len-1; i++){ cout<<"["<<path[i].first<<","<<path[i].second<<"],"; } cout<<"["<<path[len-1].first<<","<<path[len-1].second<<"]"; } int up=3; int down=0; int horizon=1; int main(){ int n,m,P; while(cin>>n>>m>>P){ vector<vector<int>> maze(n, vector<int>(m, 0)); for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ cin>>maze[i][j]; } } vector<pair<int, int>> best_path; int minP = P+1; queue<vector<int>> q; queue<vector<pair<int, int>>> path_q; // {x, y, p, from_direction} // from_direction:up-0, left-1, right-2, down-3 q.push({0, 0, 0, 0}); path_q.push({ {0, 0} }); while(!q.empty()){ // 取出最先加到队列的坐标 vector<int> node = q.front(); vector<pair<int, int>> current_path = path_q.front(); q.pop(); path_q.pop(); // 判断当前点是否是终点,记录最佳路径 if(node[0]==0 && node[1]==m-1 && node[2]<=P){ if(node[2]<minP){ best_path = current_path; minP = node[2]; } continue; } // 判断当前是否还有体力 if(node[2]>=P) continue; // 向下走一步 if(node[0]+1<n && node[3]!=3){ if(maze[node[0]+1][node[1]]==1){ q.push({node[0]+1, node[1], node[2]+down, 0}); current_path.push_back({node[0]+1, node[1]}); path_q.push(current_path); current_path.pop_back(); } } // 向右走一步 if(node[1]+1<m && node[3]!=2){ if(maze[node[0]][node[1]+1]==1){ q.push({node[0], node[1]+1, node[2]+horizon, 1}); current_path.push_back({node[0], node[1]+1}); path_q.push(current_path); current_path.pop_back(); } } // 向左走一步 if(node[1]-1>=0 && node[3]!=1){ if(maze[node[0]][node[1]-1]==1){ q.push({node[0], node[1]-1, node[2]+horizon, 2}); current_path.push_back({node[0], node[1]-1}); path_q.push(current_path); current_path.pop_back(); } } // 向上走一步 if(node[0]-1>=0 && node[3]!=0){ if(maze[node[0]-1][node[1]]==1){ q.push({node[0]-1, node[1], node[2]+up, 3}); current_path.push_back({node[0]-1, node[1]}); path_q.push(current_path); current_path.pop_back(); } } } if(best_path.empty()){ cout<<"Can not escape!"<<endl; } else{ ShowPath(best_path); } } return 0; }
#include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; int main() { // 输入数据 int n, m, P; cin >> n >> m >> P; vector<vector<int>> board(n); for(int i = 0; i < n; i++) { board[i].resize(m); for(int j = 0; j < m; j++) cin >> board[i][j]; } // 构建有向图 vector<vector<int>> graph(m * n); // 邻接矩阵[m*n][m*n] for (int i = 0; i < m * n; i++) graph[i].resize(m * n, INT32_MAX); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(i > 0 && board[i - 1][j]) // 向上的边权值为3 graph[i * m + j][(i - 1) * m + j] = 3; if(i < n - 1 && board[i + 1][j]) // 向下的边权值为0 graph[i * m + j][(i + 1) * m + j] = 0; if(j > 0 && board[i][j - 1]) // 向左的边权值为1 graph[i * m + j][i * m + j - 1] = 1; if(j < m - 1 && board[i][j + 1]) // 向右的边权值为1 graph[i * m + j][i * m + j + 1] = 1; } // Dijkstra算法求(0,0)->(0,m-1)的最短路径 vector<int> prenode(m * n); // 前驱结点 vector<int> mindist(m * n); // 最短距离 vector<bool> found(m * n, false); // 该结点是否已找到最短路径 for (int i = 0; i < m * n; i++) { prenode[i] = 0; mindist[i] = graph[0][i]; } found[0] = true; for (int v = 1; v < m * n; v++) { // 求得距离vs最近的结点vnear和最短距离min int vnear; int min = INT32_MAX; for (int j = 0; j < m * n; j++) if(!found[j] && mindist[j] < min) { min = mindist[j]; vnear = j; } if(min == INT32_MAX) // 找不到连通路径 break; found[vnear] = true; // 根据vnear修正vs到其他节点的前驱结点prenode和最短距离mindist for (int k = 0; k < m * n; k++) if(!found[k] && min != INT32_MAX && graph[vnear][k] != INT32_MAX && (min + graph[vnear][k] < mindist[k])) { prenode[k] = vnear; mindist[k] = min + graph[vnear][k]; } } // 输出(0,0)到(0,m-1)的路径 if(mindist[m - 1] > P) cout << "Can not escape!" << endl; else { stack<pair<int, int>> path; for (int i = m - 1; i != 0; i = prenode[i]) path.push({i / m, i % m}); cout << "[0,0]"; while(!path.empty()) { const auto &p = path.top(); cout << ",[" << p.first << ',' << p.second << ']'; path.pop(); } cout << endl; } return 0; }
#include <iostream> #include <vector> using namespace std; const int visited = -1; int G[10][10]; int d[4][3] = {{0,-1,1},{0,1,1},{-1,0,3},{1,0,0}}; int remain_P = -1; int n,m,P; struct Point{ int x, y; Point(int xx, int yy): x(xx), y(yy) {}; }; vector<Point> pathStack; vector<Point> path; void PrintPath(vector<Point> &path) { for(int i=0;i<path.size();i++) { cout<<"["<<path[i].x<<","<<path[i].y<<"]"; if(i<path.size()-1) cout<<","; } } void Search(int x, int y, int p) { pathStack.push_back(Point(x,y)); G[x][y] = visited; //当前点为出口 且 体力值>=0 if(x==0 && y==m-1 && P>=0){ if(p > remain_P) { remain_P = p; path = pathStack; } }else if(p>0){ //当前点不为出口 且 体力值>0 for(int i=0;i<4;i++) { int xx = x + d[i][0]; int yy = y + d[i][1]; int pp = p - d[i][2]; if(xx>=0 && xx<n && yy>=0 && yy<m && G[xx][yy]==1) Search(xx,yy,pp); } } pathStack.pop_back(); G[x][y] = 1; } int main() { cin>>n>>m>>P; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>G[i][j]; Search(0,0,P); if(remain_P != -1) { PrintPath(path); cout<<endl; }else cout<<"Can not escape!"<<endl; return 0; }
//AC代码: #include<stdio.h> #include<vector> #include<queue> #include<string.h> using namespace std; struct HeapNode{ int d,u; HeapNode(int d,int u):d(d),u(u){} bool operator<(const HeapNode &rhs) const{ return d>rhs.d; } }; struct Edge{ int from,to,dist; Edge(int u,int v,int d):from(u),to(v),dist(d){} }; int N,M; const int INF=1000000000; const int maxn=100; struct Dijkstra{ int n,m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; int d[maxn]; int p[maxn]; Dijkstra(int n):n(n){} void AddEdge(int from,int to,int dist){ edges.push_back(Edge(from,to,dist)); m=edges.size(); G[from].push_back(m-1); } void dijkstra(int s){ int i; priority_queue<HeapNode> Q; for(i=0;i<n;i++) d[i]=INF; d[s]=0; memset(done,0,sizeof(done)); Q.push(HeapNode(0,s)); while(!Q.empty()){ HeapNode x=Q.top(); Q.pop(); int u=x.u; if(done[u]) continue; done[u]=true; for(i=0;i<G[u].size();i++){ Edge &e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist){ d[e.to]=d[u]+e.dist; p[e.to]=G[u][i]; Q.push(HeapNode(d[e.to],e.to)); } } } } void path(int s,int t){ if(t!=s){ int fa=edges[p[t]].from; path(s,fa); printf("[%d,%d]",t/M,t%M); if(t/M||t%M!=M-1) printf(","); else printf("\n"); }else printf("[%d,%d],",t/M,t%M); } }; int main(){ //freopen("input.txt","r",stdin); int G[15][15],i,j,p,k,Next[4][3]={0,1,1,0,-1,1,-1,0,3,1,0,0}; for(scanf("%d%d%d",&N,&M,&p),i=0;i<N;i++) for(j=0;j<M;j++) scanf("%d",&G[i][j]); Dijkstra dijkstra(N*M); for(i=0;i<N;i++) for(j=0;j<M;j++) for(k=0;k<4;k++){ int nx=i+Next[k][0],ny=j+Next[k][1],num1=i*M+j,num2=nx*M+ny; if(nx<0||nx>=N||ny<0||ny>=M||!G[nx][ny]) continue; dijkstra.AddEdge(num1,num2,Next[k][2]); } dijkstra.dijkstra(0); if(dijkstra.d[M-1]>p) printf("Can not escape!\n"); else dijkstra.path(0,M-1); }//用dijkstra就可以了
# include <iostream> # include <vector> # include <stack> using namespace std; int res_cnt = 0; //结果数目 int max_p = -1; //初始化剩余体力 vector<int> result; //保存结果 vector<int> res_tmp; //保存中间结果 bool visited[10][10] = { 0 }; //0表示未访问过 int a[10][10] = { 0 }; void dfs(int i, int j, int p, int n, int m); int main() { int n, m, p; cin >> n >> m >> p; cin.get(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cin >> a[i][j]; cin.get(); } dfs(0, 0, p, n, m); if (res_cnt) { for (int i = 0; i < result.size() / 2 - 1; i++) cout << '[' << result[2 * i] << ',' << result[2 * i + 1] << ']' << ','; cout << '[' << result[result.size() - 2] << ',' << result[result.size() - 1] << ']' << endl; } else cout << "Can not escape!" << endl; cin.get(); } void dfs(int i, int j, int p, int n, int m) { if (i<0 || i >= n || j<0 || j >= m || p<0 || !a[i][j] || visited[i][j]) //各类边界条件 return; res_tmp.push_back(i); res_tmp.push_back(j); visited[i][j] = 1; if (i == 0 && j == m - 1) { res_cnt++; if (p > max_p) //找到剩余体力较多的方案,更新方案 { max_p = p; result.clear(); //清空 for (int i = 0; i < res_tmp.size(); i++) result.push_back(res_tmp[i]); } } else { dfs(i - 1, j, p - 3, n, m); //上 dfs(i + 1, j, p, n, m); //下 dfs(i, j - 1, p - 1, n, m); //左 dfs(i, j + 1, p - 1, n, m); //右 } res_tmp.pop_back(); //记得返回 res_tmp.pop_back(); visited[i][j] = 0; }