题目包括多组测试数据。
每组测试数据以三个整数N,M,T(00)开头,分别代表迷宫的长和高,以及公主能坚持的天数。
紧接着有M行,N列字符,由".","*","P","S"组成。其中
"." 代表能够行走的空地。
"*" 代表墙壁,redraiment不能从此通过。
"P" 是公主所在的位置。
"S" 是redraiment的起始位置。
每个时间段里redraiment只能选择“上、下、左、右”任意一方向走一步。
输入以0 0 0结束。
如果能在规定时间内救出公主输出“YES”,否则输出“NO”。
4 4 10 .... .... .... S**P 0 0 0
YES
//广搜,每个节点向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; }
广度优先遍历 #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; }
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(); } } }
//利用一个额外的标志数组和短路特性可以很简易的递归实现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;}}
/****吧怎么就内存超限了? 大家来看看 内存超限:您的程序使用了超过限制的内存 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; }
广度搜索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;
}
}
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; } }
为什么我的提交不对呀,我自己运行对着呢,各位大虾帮忙看下,问题出到哪里了?
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;
}