2
\$\begingroup\$

Challenge URL: http://acm.scu.edu.cn/soj/problem.action?id=3330

Windy has a matrix A with size N*M which only contains 0 or 1. The distance between Axy and Apq is: |x-p| + |y-q| Can you help Windy to find the minimum distance between Aij and 1? Output the sum of the minimum distance of all Aij.

Input

The first line of input is the number of test case. For each test case: The first line contains two integers N and M. The next N lines each contains M integers, Aij. There is a blank line before each test case.
1 <= N,M <= 1000
0 <= Aij <= 1
There is at least one Aij=1.

Output

For each test case output the answer on a single line.

Sample Input and output can be seen at the URL.

But this one when I use BFS, it is too slow, and I guess there can be a better implementation.

Update for a new code

I find DP can help in this problem, I passed the test case in the question, but get runtime error for the further test, please help me fix this code, thank you!

//import java.util.Queue;
import java.util.Scanner;
//import java.util.LinkedList;


//3300 BFS
public class WindyMatrix {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        int row, col, i, j, result,cnt,now;
        int[][] M = new int[1000][1000];
        int[][] DP = new int[1000][1000];
        // 0 -> 1; -1 -> 0 not get dis
        while (t != 0) {
            cnt = now = result = 0;

            row = scanner.nextInt();
            col = scanner.nextInt();
            for (i = 0; i < row; i++) {
                for (j = 0; j < col; j++) {
                    M[i][j] = scanner.nextInt();
                    if(M[i][j]==0){
                        DP[i][j] = -1;
                        cnt++;//cnt for 0 position
                    }
                    else {
                        DP[i][j] = 0;
                    }
                }
            }

            while (cnt!=0) {
                // 找now进行+1
                for (i = 0; i < row; i++) {
                    for (j = 0; j < col; j++) {
                        if(DP[i][j]==now){
                            if(i-1>=0 && DP[i-1][j]==-1){
                                DP[i-1][j] = now+1;
                                result+=now+1;
                                cnt--;
                            }
                            if(i+1<row && DP[i+1][j]==-1){
                                DP[i+1][j] = now+1;
                                result+=now+1;
                                cnt--;
                            }
                            if(j-1>=0 && DP[i][j-1]==-1){
                                DP[i][j-1] = now+1;
                                result+=now+1;
                                cnt--;
                            }
                            if(j+1<col&&DP[i][j+1]==-1){
                                DP[i][j-1] = now+1;
                                result+=now+1;
                                cnt--;
                            }
                        }
                    }
                }
                now++;
            }

            System.out.println(result);
            t--;
        }
    }
}

older one, time exceed.

import java.util.Queue;
import java.util.Scanner;
import java.util.LinkedList;

// 3300 BFS
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        int row, col, i, j, result, distance, cnt, nextcnt,t1,t2;
        int[][] M = new int[1000][1000];
        Queue list = new LinkedList();
        boolean find_flag;
        while (t != 0) {
            result = 0;
            row = scanner.nextInt();
            col = scanner.nextInt();
            for (i = 0; i < row; i++) {
                for (j = 0; j < col; j++) {
                    M[i][j] = scanner.nextInt();
                }
            }
            // compute the distance for every 0
            for (i = 0; i < row; i++) {
                for (j = 0; j < col; j++) {
                    if (M[i][j] == 0) {
                        // BFS
                        distance = 0;
                        cnt = 0;
                        if (j - 1 >= 0) {
                            list.add(i);
                            list.add(j - 1);
                            cnt++;
                        }
                        if (j + 1 < col) {
                            cnt++;
                            list.add(i);
                            list.add(j + 1);
                        }
                        if (i - 1 >= 0) {
                            cnt++;
                            list.add(i-1);
                            list.add(j);
                        }
                        if (i + 1 < row) {
                            cnt++;
                            list.add(i+1);
                            list.add(j);
                        }
                        nextcnt = 0;
                        find_flag = false;
                        while (true) {
                            distance++;
                            for (i = 0; i < cnt; i++) {
                                t1 = (int) list.poll();
                                t2 = (int) list.poll();
                                if (M[t1][t2] == 1) {
                                    find_flag = true;
                                    break;
                                }
                                if (t2 - 1 >= 0) {
                                    list.add(t1);
                                    list.add(t2-1);
                                    nextcnt++;
                                }
                                if (t2 + 1 < col) {
                                    list.add(t1);
                                    list.add(t2+1);
                                    nextcnt++;
                                }
                                if (t1 - 1 >= 0) {
                                    nextcnt++;
                                    list.add(t1-1);
                                    list.add(t2);
                                }
                                if (t1 + 1 < row) {
                                    nextcnt++;
                                    list.add(t1+1);
                                    list.add(t2);
                                }
                            }
                            if (find_flag) {
                                break;
                            }
                            cnt = nextcnt;
                            nextcnt = 0;
                        }
                        list.clear();
                        result += distance;
                    }
                }
            }
            System.out.println(result);
            t--;
        }
    }
}

So if I want to make it finish in the time frame, what can be improved?

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to CodeReview I hope you get some good answers. \$\endgroup\$ – pacmaninbw Jun 1 '16 at 13:29
  • \$\begingroup\$ Sample Input and output can be seen at the URL. I can see no URL \$\endgroup\$ – Bogdan Mart Jun 1 '16 at 15:32
  • \$\begingroup\$ sorry, it is url on challenge, it is not obvious, I fix it. \$\endgroup\$ – ljy Jun 1 '16 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.