首页 > 试题广场 >

Hero

[编程题]Hero

热度指数：1437 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

500年前，nowcoder是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。突然有一天，nowcoder 心爱的公主被魔王困在了一个巨大的迷宫中。nowcoder 听说这个消息已经是两天以后了，他知道公主在迷宫中还能坚持T天，他急忙赶到迷宫，开始到处寻找公主的下落。时间一点一点的过去，nowcoder 还是无法找到公主。最后当他找到公主的时候，美丽的公主已经死了。从此nowcoder 郁郁寡欢，茶饭不思，一年后追随公主而去了。T_T 500年后的今天，nowcoder 托梦给你，希望你帮他判断一下当年他是否有机会在给定的时间内找到公主。他会为你提供迷宫的地图以及所剩的时间T。请你判断他是否能救出心爱的公主。

输入描述:

题目包括多组测试数据。
每组测试数据以三个整数N,M,T(00)开头，分别代表迷宫的长和高，以及公主能坚持的天数。
紧接着有M行，N列字符，由"."，"*"，"P"，"S"组成。其中
"." 代表能够行走的空地。
"*" 代表墙壁，redraiment不能从此通过。
"P" 是公主所在的位置。
"S" 是redraiment的起始位置。
每个时间段里redraiment只能选择“上、下、左、右”任意一方向走一步。
输入以0 0 0结束。

输出描述:

如果能在规定时间内救出公主输出“YES”，否则输出“NO”。

示例1

输入

4 4 10
....
....
....
S**P
0 0 0

输出

YES

算法知识视频讲解

L0L

//广搜，每个节点向4个方向发散，并且标记，直到发散节点是P节点
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct pos {
	int x;
	int y;
	int time;
};
int main() {
	int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};//代表四个方向
	int n,m,t;
	bool ok;
	while(cin>>n>>m>>t) {
		if(n==0&&m==0&&t==0)	return 0;
		ok=false;
		vector<vector<char> > map(m,vector<char>(n));
		queue<pos> find;
		pos start,goal;
	
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				cin>>map[i][j];
				if(map[i][j]=='S') {
					start.x=i;
					start.y=j;
					start.time=0;
				} else if(map[i][j]=='P') {
					goal.x=i;
					goal.y=j;
				}
			}
		}

		find.push(start);
		map[start.x][start.y]='*';
		pos cur;
		
		while(!find.empty()) {
			cur=find.front();
			find.pop();
			if(cur.x==goal.x&&cur.y==goal.y&&cur.time<=t) {
				cout<<"YES"<<endl;
				ok=true;
				break;
			}
			for(int i=0; i<4; i++) {
				pos nbr;
				nbr.x=cur.x+dir[i][0];
				nbr.y=cur.y+dir[i][1];
				nbr.time=cur.time+1;
				if(nbr.x>=0&&nbr.x<m&&nbr.y>=0&&nbr.y<n&&nbr.time<=t&&map[nbr.x][nbr.y]!='*') {
					find.push(nbr);
					map[nbr.x][nbr.y]='*';
				}
			}
		}
		if(!ok){
			cout<<"NO"<<endl;
		}
		map.clear();
	}
	return 0;
}

编辑于 2015-10-18 10:10:20 回复(0)

Cavs

广度优先遍历
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

using namespace std;

bool check(vector<vector<char>>& maze, int x, int y)
{
	if (x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == '*') return false;
	else return true;
}

bool canReach(vector<vector<char>>& maze, vector<vector<bool>>& visited, int x, int y, int T)
{
	vector<pair<int, int>> cur;
	cur.emplace_back(x, y);
	visited[x][y] = true;

	while (T > 0 && !cur.empty())
	{
		vector<pair<int, int>> next;
		for (auto& pr : cur)
		{
			int x = pr.first, y = pr.second;
			if (check(maze, x - 1, y) && !visited[x - 1][y])
			{
				if (maze[x - 1][y] == 'P') return true;
				visited[x - 1][y] = true;
				next.emplace_back(x - 1, y);
			}
			if (check(maze, x + 1, y) && !visited[x + 1][y])
			{
				if (maze[x + 1][y] == 'P') return true;
				visited[x + 1][y] = true;
				next.emplace_back(x + 1, y);
			}
			if (check(maze, x, y - 1) && !visited[x][y - 1])
			{
				if (maze[x][y - 1] == 'P') return true;
				visited[x][y - 1] = true;
				next.emplace_back(x, y - 1);
			}
			if (check(maze, x, y + 1) && !visited[x][y + 1])
			{
				if (maze[x][y + 1] == 'P') return true;
				visited[x][y + 1] = true;
				next.emplace_back(x, y + 1);
			}
		}
		cur = next;
		--T;
	}

	return false;
}

int main(int argc, char** argv)
{
	int n,m,T;
	while (cin >> n >> m >> T && n > 0 && m > 0 && T > 0)
	{
		int sx, sy;
		vector<vector<char>> maze(m, vector<char>(n));
		vector<vector<bool>> visited(m, vector<bool>(n,false));
		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				cin >> maze[i][j];
				if (maze[i][j] == 'S') { sx = i, sy = j; }
			}
		}
		if (canReach(maze,visited, sx, sy, T)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}

	return 0;
}

发表于 2017-07-10 10:47:10 回复(0)

讨鬼


import java.util.Random; import java.util.Scanner; import java.util.Stack; import java.util.concurrent.Exchanger; class Main
{ enum state
    { LEFT, RIGHT, UP, DOWN;
    } public static void getPro(final char[][] chars,int lifetime,final int m,final int n)
    {
        state state=null; int win=0; class Point
        { int hang; int lie; int left=0; int right=0; int up=0; int down=0; public Point(int hang,int lie)
            { this.hang=hang; this.lie=lie;
                init();
            } public void init()
            { if(hang==m-1||chars[hang+1][lie]=='*')
                { down=1;
                } if(hang==0||chars[hang-1][lie]=='*')
                { up=1;
                } if(lie==n-1||chars[hang][lie+1]=='*')
                { right=1;
                } if(lie==0||chars[hang][lie-1]=='*')
                { left=1;
                }
            } @Override  public boolean equals(Object obj) { // return super.equals(obj);  Point p=(Point)obj; if(p.hang==this.hang&&p.lie==this.lie)
                { return true;
                } return false;
            }
        }
        Stack<Point> stack=new Stack<Point>(); //扫描一遍，确定P和S的位置  int x1=0,y1=0,x2=0,y2=0; for(int i=0;i<chars.length;i++)
        { char[] array=chars[i]; for(int j=0;j<array.length;j++)
            { if(array[j]=='S')
                {
                    x1=i;
                    y1=j;
                } if(array[j]=='P')
                {
                    x2=i;
                    y2=j;
                }
            }
        } //表示优先在左右方向选择哪个  Point src=new Point(x1,y1);
        Point des=new Point(x2,y2);
        stack.add(src);
        state[] states=new state[4]; while (!stack.isEmpty())
        {
            Point p=stack.peek(); if(p.hang==des.hang&&p.lie==des.lie)
            {
                win=1; break;
            } if(p.hang==des.hang)
            { if(des.lie>p.lie)
                {
                    states[0]=state.RIGHT;
                    states[3]=state.LEFT;
                    states[1]=state.UP;
                    states[2]=state.DOWN;
                } else  {
                    states[3]=state.RIGHT;
                    states[0]=state.LEFT;
                    states[1]=state.UP;
                    states[2]=state.DOWN;
                }
            } if(p.lie==des.lie)
            { if(des.hang>p.hang)
                {
                    states[0]=state.DOWN;
                    states[3]=state.UP;
                    states[1]=state.LEFT;
                    states[2]=state.RIGHT;
                } else  {
                    states[3]=state.DOWN;
                    states[0]=state.UP;
                    states[1]=state.LEFT;
                    states[2]=state.RIGHT;
                }
            } if(p.hang!=des.hang&&p.lie!=des.lie)
            { int gap=Math.abs(des.hang-p.hang)-Math.abs(des.lie-p.lie); int i; int j; if(gap>=0)
                {
                    i=0;
                    j=1;
                } else  {
                    i=1;
                    j=0;
                } if(des.hang>p.hang)
               {
                   states[i]=state.DOWN;
                   states[i+2]=state.UP;
               } else  {
                   states[i+2]=state.DOWN;
                   states[i]=state.UP;
               } if(des.lie>p.lie)
                {
                    states[j]=state.RIGHT;
                    states[j+2]=state.LEFT;
                } else  {
                    states[j+2]=state.RIGHT;
                    states[j]=state.LEFT;
                }
            } int size=stack.size(); for(int i=0;i<states.length;i++)
            {
                state state1=states[i]; if(state1==state.RIGHT&&p.right==0)
                {
                    Point point=new Point(p.hang,p.lie+1);
                    point.left=1;
                    p.right=1;
                    stack.add(point); break;
                } if(state1==state.LEFT&&p.left==0)
                {
                    Point point=new Point(p.hang,p.lie-1);
                    point.right=1;
                    p.left=1;
                    stack.add(point); break;
                } if(state1==state.DOWN&&p.down==0)
                {
                    Point point=new Point(p.hang+1,p.lie);
                    point.up=1;
                    p.down=1;
                    stack.add(point); break;
                } if(state1==state.UP&&p.up==0)
                {
                    Point point=new Point(p.hang-1,p.lie);
                    point.down=1;
                    p.up=1;
                    stack.add(point); break;
                }
            } if(stack.size()==size) {
                stack.pop();
            } else  {
                Point point1=stack.pop(); if(!stack.contains(point1))
                {
                    stack.add(point1);
                }
            }
        } for(int i=0;i<stack.size();i++)
        { // System.out.println(stack.get(i).hang+"   "+stack.get(i).lie);  } if(lifetime>=stack.size()-1&&win==1)
        {
            System.out.println("YES");
        } else  {
            System.out.println("NO");
        }
    } public static void main(String[] args)
    {
        Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int lifetime=scanner.nextInt(); while (n!=0||m!=0||lifetime!=0)
        { char[][] chars=new char[m][n]; for(int i=0;i<m;i++)
           {
               String s=scanner.next(); char[] chars1= s.toCharArray(); for(int j=0;j<n;j++)
               {
                   chars[i][j]=chars1[j];
               }
           } getPro(chars, lifetime, m, n);
             n=scanner.nextInt();
             m=scanner.nextInt();
             lifetime=scanner.nextInt();
        }
    }
}

发表于 2015-11-08 19:05:05 回复(0)

classObject


	//利用一个额外的标志数组和短路特性可以很简易的递归实现



	import java.util.Scanner;



	public class Main{



	    public static void main(String[] args){



	        Scanner in=new Scanner(System.in);



	        while(true){



	            int n=in.nextInt();



	            int m=in.nextInt();



	            int t=in.nextInt();



	            if(n==0&& m==0&& t==0) break;



	            int stai=0;



	            int staj=0;



	            char[][] arr=new char[m][n];



	            for(int i=0;i<m;i++){



	                String s=in.next();



	                for(int j=0;j<n;j++){



	                    arr[i][j]=s.charAt(j);



	                    if(arr[i][j]=='S'){



	                        stai=i;



	                        staj=j;



	                    }



	                }



	            }



	            boolean[][] vis=new boolean[m][n];



	            if(dfs(arr,vis,t,stai,staj)) System.out.println("YES");



	            else System.out.println("NO");



	        }



	        in.close();



	    }



	    static boolean dfs(char[][] arr,boolean[][] vis,int t,int i,int j){



	        if(t<0|| i<0|| j<0|| i>=arr.length || j>=arr[0].length) return false;



	        if(vis[i][j] || arr[i][j]=='*') return false;



	        if(arr[i][j]=='P') return true;



	        vis[i][j]=true;



	        boolean b=dfs(arr,vis,t-1,i,j+1) || dfs(arr,vis,t-1,i-1,j) || dfs(arr,vis,t-1,i,j-1) || dfs(arr,vis,t-1,i+1,j);



	        vis[i][j]=false;



	        return b;



	    }



	}

发表于 2018-08-28 21:28:24 回复(0)

1hani1

/****吧怎么就内存超限了？ 大家来看看 内存超限:您的程序使用了超过限制的内存 case通过率为0.00% */
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
    int m,n,t;
    int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    while(cin>>m>>n>>t && m)
    {
        queue<pair<int, int>> pos;
        pair<int,int> d;
        vector<vector<char> > map(m,vector<char>(n));
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='S')
                    pos.push({i,j});
                else if(map[i][j]=='P')
                    d={i,j};
            }
        bool ans=0;
        while(!pos.empty() && t--)
        {
            int num =pos.size();
            while(num--)
            {
                pair<int,int> p =pos.front();
                pos.pop();
                if(p==d)
                {
                    ans=1;
                    t=0;
                    break;
                }
                int x=p.first;
                int y=p.second;
                map[x][y]='*';
                for(int i=0;i<4;i++)
                {
                    int nx=x+move[i][0];
                    int ny=y+move[i][1];
                    if(nx>=0 && nx<m && ny>=0 && ny<n && 
                       (map[nx][ny]=='.' || map[nx][ny]=='P'))
                        pos.push({nx,ny});
                }
            }
        }
        cout<<(ans?"YES":"NO")<<endl;
    }
    return 0;
}

发表于 2018-07-29 14:48:06 回复(0)

牛客6369791号

广度搜索bfs
import java.util.Queue;
import java.util.LinkedList;
import java.util.Scanner;
public class Main{
    static boolean[][] visited;
    static int[][] directions={{0,1},{0,-1},{1,0},{-1,0}};
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String s = in.nextLine();
            if("0 0 0".equals(s)){
                break;
            }
            String[] sc = s.split(" ");
            if(sc.length!=3){
               System.out.println("NO");
               break;
            }
            int N = Integer.parseInt(sc[0]);
            int M = Integer.parseInt(sc[1]);
            int T = Integer.parseInt(sc[2]);
            char[][] ch = new char[M][N];
            miNode start=null;
            miNode end=null;
            visited = new boolean[M][N];
            for(int i=0;i<M;i++){
                String sr = in.nextLine();
                for(int j=0;j<N;j++){
                    ch[i][j]=sr.charAt(j);
                    if(ch[i][j]=='S'){
                        start = new miNode(i,j,0);
                    }
                    if(ch[i][j]=='P'){
                        end = new miNode(i,j,0);
                    }
                }
            }
            bfs(ch,M,N,T,start,end);
        }
        in.close();
    }
    private static void bfs(char[][] ch,int M,int N,int T,miNode start,miNode end){
        Queue<miNode> queue = new LinkedList<miNode>();
        queue.add(start);
        visited[start.x][start.y]=true;
        boolean flag =false;
        while(!queue.isEmpty()){
            miNode cur = queue.poll();
            if(cur.x==end.x&&cur.y==end.y&&cur.step<=T){
                flag=true;
                break;
            }
            for(int i=0;i<4;i++){
                miNode next = new miNode(cur.x+directions[i][0],cur.y+directions[i][1],cur.step+1);
                if(next.x>=0&&next.x<M&&next.y>=0&&next.y<N&&ch[next.x][next.y]!='*'&&visited[next.x][next.y]!=true){
                    queue.add(next);
                    visited[next.x][next.y]=true;
                }
            }
        }
        if(flag==true){
            System.out.println("YES");
        }
        else{
            System.out.println("NO");
        }
    }
}
class miNode{
    int x;
    int y;
    int step;
    public miNode(int x,int y, int step){
        this.x=x;
        this.y=y;
        this.step=step;
    }
}

编辑于 2017-04-05 12:55:18 回复(0)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextLine()) {
			String s = sc.nextLine();
			if(s.equals("0 0 0")) break;
			String[] split = s.trim().split("\\s+");
			int n = Integer.parseInt(split[0]);
			int m = Integer.parseInt(split[1]);
			int t = Integer.parseInt(split[2]);
			Character[][] arr = new Character[m][n];
			Node start = new Node();
			Node end = new Node();
			for (int i = 0; i < m; i ++ ) {
				String s1 = sc.nextLine();
				for (int j = 0; j < n; j ++ ) {
					arr[i][j] = s1.charAt(j);
					if(arr[i][j] == 'S') {
						start.x = i;
						start.y = j;
					}
					if(arr[i][j] == 'P') {
						end.x = i;
						end.y = j;
					}
				}
			}
			int[][] direction = {{0, 1}, {0, - 1}, {1, 0}, { - 1, 0}};
			bfs(arr, n, m, t, start, end, direction);
		}
	}
	public static void bfs(Character[][] arr, int n, int m, int t, Node start, Node end, int[][] direction) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(start);
		boolean[][] visited = new boolean[m][n];
		visited[start.x][start.y] = true;
		boolean isFinded = false;
		while ( ! queue.isEmpty()) {
			Node cur = queue.poll();
			if(cur.x == end.x && cur.y == end.y && cur.time <= t) {
				isFinded = true;
				break;
			}
			for (int i = 0; i < 4; i ++ ) {
				Node next = new Node();
				next.x = cur.x + direction[i][0];
				next.y = cur.y + direction[i][1];
				next.time = cur.time + 1;
				if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n && ! visited[next.x][next.y] && arr[next.x][next.y] != '*') {
					queue.add(next);
					visited[next.x][next.y] = true;
				}
			}
		}
		if(isFinded) System.out.println("YES");
		else System.out.println("NO");
	}
	static class Node {
		int x;
		int y;
		int time;
	}
}

发表于 2016-10-07 16:03:28 回复(0)

hofighter

答案错误:您提交的程序没有通过所有的测试用例

测试用例:
S**P

对应输出应该为:

YES

你的输出为:

这个测试用例不就应该输出No吗？

发表于 2016-01-20 12:20:30 回复(0)

镜中阿猫

为什么我的提交不对呀，我自己运行对着呢，各位大虾帮忙看下，问题出到哪里了？
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
static int N;
static int M;
public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  while (sc.hasNextLine()) {
   N=sc.nextInt();
   M=sc.nextInt();
  int T=sc.nextInt();
  if(N==0&&M==0&&T==0){
   break;
  }
  Node start=new Node();
  Node end=new Node();
  String [][] map=new String[N][M];
  for(int i=0;i<N;i++){
   String str=sc.next();
   for(int j=0;j<M;j++){
    map[i][j]=String.valueOf(str.charAt(j));
    if(map[i][j].equals("S")){
     start.x=i;
     start.y=j;
    }
    if(map[i][j].equals("P")){
     end.x=i;
     end.y=j;
    }
   }
  }
  System.out.println(dfs(map, start, end));
  if (T>=dfs(map, start, end)) {
   System.out.println("YES");

  }else{
   System.out.println("NO");
  }
  }
}
private static int dfs(String[][] map,Node start,Node end) {
  int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};
  int [][] step=new int[N][M];
  Node local=new Node();
  LinkedList<Node> lik=new LinkedList<Node>();
  lik.add(start);
  while(!lik.isEmpty()){
   local=lik.removeFirst();
   if(local.x==end.x&&local.y==end.y){
    return step[local.x][local.y];
   }
   else{
   for(int i=0;i<4;i++){
    Node nbr=new Node();
    nbr.x=local.x+dir[i][0];
    nbr.y=local.y+dir[i][1];
    if(nbr.x>=0&&nbr.x<M&&nbr.y>=0&&nbr.y<N){
     if((map[nbr.x][nbr.y].equals(".")&&step[nbr.x][nbr.y]==0)||(map[nbr.x][nbr.y].equals("P")&&step[nbr.x][nbr.y]==0)){
     step[nbr.x][nbr.y]=step[local.x][local.y]+1;
     lik.add(nbr);
     }
    }
   }
  }
  }
  return 0;

}
}
class Node{
int x;
int y;
}