oj上的一道在二维坐标图中的迪杰斯特拉找最短路径的题,我用许多种测试数据跑过我的代码,但是评测机说有很多组数据runtime error,实在是找不到问题所在了,所以请求各位大神帮个忙,谢谢了
题目如下
2S时限 , 256空间限制 , N和M都不大于2000
import java.io.*;
import java.util.*;
class InputReader {
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(stream), 327680);
tokenizer = null;
}
public boolean hasNext(){
while(tokenizer == null || !tokenizer.hasMoreElements())
{
try
{
tokenizer = new StringTokenizer(br.readLine());
}
catch(Exception e)
{
return false;
}
}
return true;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
try {
int c = br.read();
while (c <= 32) {
c = br.read();
}
boolean negative = false;
if (c == '-') {
negative = true;
c = br.read();
}
int x = 0;
while (c > 32) {
x = x * 10 + c - '0';
c = br.read();
}
return negative ? -x : x;
}catch(IOException e){
return -1;
}
}
public long nextLong() {
try {
int c = br.read();
while (c <= 32) {
c = br.read();
}
boolean negative = false;
if (c == '-') {
negative = true;
c = br.read();
}
long x = 0;
while (c > 32) {
x = x * 10 + c - '0';
c = br.read();
}
return negative ? -x : x;
}catch(IOException e){
return -1;
}
}
}//快速读入和输出
class Node{
int row;
int col;
int w;
public Node(int row , int col) {
this.row = row;
this.col = col;
}
}//节点类
class nodeHeap{
Node []Heap;
int size;
int tmpSize;
public nodeHeap(int max) {
size = max;
Heap = new Node [size];
tmpSize = 0;
Heap[0] = new Node(0 , 0);
Heap[0].w = -1;
}
public void swap(int a , int b) {
Node tmp;
tmp = Heap[a];
Heap[a] = Heap[b];
Heap[b] = tmp;
}
public void up(int n) {
while(n / 2 >= 1) {
if(Heap[n].w < Heap[n / 2].w) {
swap(n , n / 2);
n = n / 2;
}
else break;
}
}
public void push(Node i) {
tmpSize ++;
Heap[tmpSize] = i;
int tmp = tmpSize;
up(tmp);
}
public Node peek() {
return Heap[1];
}
public void down(int i) {
while(i * 2 <= tmpSize || i > tmpSize) {
int I = 2 * i;
if(I < tmpSize && Heap[I].w > Heap[I + 1].w)
I ++;
if(Heap[I].w > Heap[i].w){
return;
}
else {
swap(i , I);
i = I;
}
}
}
public Node pop() {
swap(1 , tmpSize);
tmpSize --;
if(tmpSize > 0) {
down(1);
}
return Heap[tmpSize + 1];
}
}//自己写的堆
public class Main {
static PrintWriter out;
static InputReader in;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
out = new PrintWriter(System.out);
in = new InputReader(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] map = new int[n][m];//用于储存数据
Node root = null;//根节点
nodeHeap heap = new nodeHeap(200000);//初始化堆
boolean[][] visited = new boolean[n][m];//用于判断某个点是否遍历到过
for(int i = 0 ; i < n ; i ++) {
String A = in.next();
for(int j = 0 ; j < m ; j ++) {
char c = A.charAt(j);
if(c == 'H') {
map[i][j] = 1;
visited[i][j] = true;
root = new Node(i , j);
heap.push(root);
}
else if(c == 'B')
map[i][j] = 2;
else if(c == 'R')
map[i][j] = 3;
else if(c == 'W')
map[i][j] = 4;
else if(c == 'S')
map[i][j] = 5;
}
}//储存数据
while(heap.tmpSize > 0) {
Node tmp = heap.pop();
if(map[tmp.row][tmp.col] == 5) {
out.println(tmp.w);
break;
}//若当前节点为S 则结束循环并输出距离
if(tmp.row - 1 >= 0)
if(visited[tmp.row - 1][tmp.col] == false && map[tmp.row - 1][tmp.col] != 4) {
visited[tmp.row - 1][tmp.col] = true;
Node node = new Node(tmp.row - 1 , tmp.col);
if(map[tmp.row - 1][tmp.col] == 1 || map[tmp.row - 1][tmp.col] == 3 || map[tmp.row - 1][tmp.col] == 5)
node.w = tmp.w + 1;
else if(map[tmp.row - 1][tmp.col] == 2)
node.w = tmp.w + 2;
heap.push(node);
}
if(tmp.row + 1 <= n - 1)
if(visited[tmp.row + 1][tmp.col] == false && map[tmp.row + 1][tmp.col] != 4) {
visited[tmp.row + 1][tmp.col] = true;
Node node = new Node(tmp.row + 1 , tmp.col);
if(map[tmp.row + 1][tmp.col] == 1 || map[tmp.row + 1][tmp.col] == 3 || map[tmp.row + 1][tmp.col] == 5)
node.w = tmp.w + 1;
else if(map[tmp.row + 1][tmp.col] == 2)
node.w = tmp.w + 2;
heap.push(node);
}
if(tmp.col - 1 >= 0)
if(visited[tmp.row][tmp.col - 1] == false && map[tmp.row][tmp.col - 1] != 4) {
visited[tmp.row][tmp.col - 1] = true;
Node node = new Node(tmp.row , tmp.col - 1);
if(map[tmp.row][tmp.col - 1] == 1 || map[tmp.row][tmp.col - 1] == 3 || map[tmp.row][tmp.col - 1] == 5)
node.w = tmp.w + 1;
else if(map[tmp.row][tmp.col - 1] == 2)
node.w = tmp.w + 2;
heap.push(node);
}
if(tmp.col + 1 <= m - 1)
if(visited[tmp.row][tmp.col + 1] == false && map[tmp.row][tmp.col + 1] != 4) {
visited[tmp.row][tmp.col + 1] = true;
Node node = new Node(tmp.row , tmp.col + 1);
if(map[tmp.row][tmp.col + 1] == 1 || map[tmp.row][tmp.col + 1] == 3 || map[tmp.row][tmp.col + 1] == 5)
node.w = tmp.w + 1;
else if(map[tmp.row][tmp.col + 1] == 2)
node.w = tmp.w + 2;
heap.push(node);
}
}//周围四个节点生成并更新距离
out.close();
}
}