请求各位大神帮忙 java语言 一道迪杰斯特拉找最短路径的题目求问代码bug 5C

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();
    }

}


1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问