SamChien's blog-山姆謙的技術筆記

2013年6月3日星期一

N-Queen

Java code:

import java.util.Scanner;

public class N_Queen {
    static int n;
    static int countQueen = 0;
    static int ansCount = 0;
    static boolean[] colHasQueen, leftSlashHasQueen, rightSlashHasQueen;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        try {
            System.out.print("請輸入n: ");
            n = sc.nextInt();
        } finally {
            sc.close();
        }
        colHasQueen = new boolean[n];
        leftSlashHasQueen = new boolean[2 * n - 1];
        rightSlashHasQueen = new boolean[2 * n - 1];
        findQueen(0, 0);
        System.out.println("總共有" + ansCount + "組解");
    }

    private static void findQueen(int row, int col) {
        if (countQueen == n)
            ansCount++;
        else if (col < n) {
            if (!colHasQueen[col] && !leftSlashHasQueen[row - col + n - 1] &&
                    !rightSlashHasQueen[row + col]) {
                colHasQueen[col] = true;
                leftSlashHasQueen[row - col + n - 1] = true;
                rightSlashHasQueen[row + col] = true;
                countQueen++;
                findQueen(row + 1, 0);
                colHasQueen[col] = false;
                leftSlashHasQueen[row - col + n - 1] = false;
                rightSlashHasQueen[row + col] = false;
                countQueen--;
            }
            findQueen(row, col + 1);
        }
    }
}

範例輸入輸出:

此程式解決的問題是經典的n-queen問題，三個布林陣列存的分別是行, 左斜線, 右斜線有沒有被擺過皇后，之所以沒有存列有無擺過皇后是因為這列擺過皇后之後，直接換下一列，所以沒有會碰到同一列的可能。若放置此位置後無法找到皇后共存的組合，則此皇后會往右移一格，若皇后移到此列的盡頭都沒有位置可以擺放則直接回到上一列更改皇后的位置，因為是在n*n的棋盤上擺放n個皇后，所以不可能有任何一列沒有被擺到皇后。

輸入為一個整數n，輸出則為總共有多少種擺放的方式，並沒有去除掉對稱的情況。

2013年5月10日星期五

簡單校園導覽程式

Java code:

import java.util.Arrays;
import java.util.Scanner;

public class FjuMap {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int startVertex;
        int endVertex;
        String[] names = {"利瑪竇大樓", "伯達樓", "樹德樓", "羅耀拉大樓", "濟時樓", "仁愛學苑", "聖心學苑", "信義/和平學苑/心園", "法園(社會服務中心)/仁園", "創新育成中心"};
        int[][] path = new int[10][10];
        int[][] graph =
                {{0, 13, Integer.MAX_VALUE, 25, Integer.MAX_VALUE, 27, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {13, 0, 10 , 20, Integer.MAX_VALUE, 35, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, 10, 0, 12, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {25, 20, 12, 0, 20, 22, Integer.MAX_VALUE, 28, 27, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 20, 0, 25, Integer.MAX_VALUE, Integer.MAX_VALUE, 16, Integer.MAX_VALUE},
                {27, 35, Integer.MAX_VALUE, 22, 25, 0, 9, 9, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 9, 0, 8, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 28, Integer.MAX_VALUE, 9, 8, 0, 10, 12},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 27, 16, Integer.MAX_VALUE, Integer.MAX_VALUE, 10, 0, 7},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 12, 7, 0}};
        
        for (int[] i: path)
            Arrays.fill(i, -1);
        for (int i=0; i<graph.length; i++) {
            for (int j=0; j<graph.length; j++) {
                for (int k=0; k<graph.length; k++) {
                    if (!(graph[i][k] == Integer.MAX_VALUE) && !(graph[k][j] == Integer.MAX_VALUE)) {
                        int newWeight = graph[i][k] + graph[k][j];
                        
                        if (newWeight < graph[i][j]) {
                            graph[i][j] = newWeight;
                            path[i][j] = k;
                        }
                    }
                }
            }
        }
        System.out.println("地點清單:");
        System.out.println("-----------------------");
        for (int i=0; i<names.length; i++)
        System.out.println(i + "." + names[i]);
        System.out.println("-----------------------");
        try {
            while (true) {
                System.out.print("請輸入起點編號(輸入10結束):");
                startVertex = sc.nextInt();
                if (startVertex == 10)
                    break;
                System.out.print("請輸入終點編號:");
                endVertex = sc.nextInt();
                System.out.print("最短路徑:");
                System.out.print(names[startVertex]);
                tracePath(path, names, startVertex, endVertex);
                System.out.println("->" + names[endVertex] + "\n");
            }
        } finally {
            sc.close();
        }
    }

    private static void tracePath(int[][] path, String[] names, int startVertex, int endVertex) {
        if (path[startVertex][endVertex] != -1) {
            tracePath(path, names, startVertex, path[startVertex][endVertex]);
            System.out.print("->" + names[path[startVertex][endVertex]]);
            tracePath(path, names, path[startVertex][endVertex], endVertex);
        }
    }
}

範例輸入輸出:

抱歉沒空說明程式碼，只能說明一下輸入輸出的部份。首先依照地點清單輸入起點編號，再輸入終點編號，程式就會印出最短路徑，若在起點編號那裡輸入10，程式就會結束。

2013年5月9日星期四

Dijkstra's Algorithm

Java code:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertexNum;
        Set<Integer> used = new HashSet<Integer>();
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<Integer, Map<Integer, Integer>>();
        Map<Integer, Integer> shortestPath = new HashMap<Integer, Integer>();
        int startVertex;
        
        try {
            System.out.print("please input the number of total vertexes:");
            vertexNum = sc.nextInt();
            System.out.println("please input the graph:");
            for (int i=1; i<=vertexNum; i++)
                graph.put(i, new HashMap<Integer, Integer>());
            for (int i=1; i<=vertexNum; i++) {
                for (int j=1; j<=vertexNum; j++) {
                    String input = sc.next();
                    
                    if (input.equals("i"))
                        graph.get(i).put(j, Integer.MAX_VALUE);
                    else
                        graph.get(i).put(j, Integer.parseInt(input));
                }
            }
            System.out.print("please input the start vertex:");
            startVertex = sc.nextInt();
        } finally {
            sc.close();
        }
        for (int i=1; i<=vertexNum; i++)
            shortestPath.put(i, graph.get(startVertex).get(i));
        used.add(startVertex);
        while (true) {
            int nearestVertex = -1;
            int smallestWeight = Integer.MAX_VALUE;
            
            for (int i=1; i<=vertexNum; i++) {
                if (!used.contains(i) && shortestPath.get(i) < smallestWeight) {
                    nearestVertex = i;
                    smallestWeight = shortestPath.get(i);
                }
            }
            used.add(nearestVertex);
            if (used.size() == vertexNum)
                break;
            for (int i=1; i<=vertexNum; i++) {
                if (graph.get(nearestVertex).get(i) != 0 && graph.get(nearestVertex).get(i) != Integer.MAX_VALUE) {
                    int newPath = shortestPath.get(nearestVertex) + graph.get(nearestVertex).get(i);
                    
                    if (newPath < shortestPath.get(i))
                        shortestPath.put(i, newPath);
                }
            }
        }
        System.out.println("shortest path from v" + startVertex + " to all other vertexes:");
        for (int i=1; i<=vertexNum; i++)
            System.out.printf("%4s", "v" + i);
        System.out.println();
        for (int i=1; i<=vertexNum; i++)
            System.out.printf("%4d", shortestPath.get(i));
        System.out.println();
    }
}

範例輸入輸出:

抱歉沒空說明程式碼，只能說明一下輸入輸出的部份。首先輸入圖形上總共點的數量，再輸入相鄰矩陣，橫軸表示點1~點10，縱軸也是表示點1~點10，輸入的是點到點之間的權重，若輸入i表示這兩點不相連，也就是權重無限大，最後再輸入以哪個點當作起點，程式會找出由這個點到其他所有點的最短距離。輸出結果表示由出發點到各點的距離。本範例輸入是採用課本習題2的圖，所以可以參照課本的圖方便了解。

Kruskal's Algorithm

Java code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class Edge implements Comparable<Edge> {
    int startVertex, endVertex, weight;

    @Override
    public int compareTo(Edge otherEdge) {
        if (weight < otherEdge.weight)
            return -1;
        else if (weight == otherEdge.weight)
            return 0;
        else
            return 1;
    }
}

public class KruskalAlgorithm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertexNum;
        int countEdge;
        int totalEdge;
        List<Edge> allEdgeList = new ArrayList<Edge>();
        Map<Integer, Map<Integer, Integer>> minSpanTree = new HashMap<Integer, Map<Integer, Integer>>();
        
        try {
            System.out.print("please input the number of total vertexes:");
            vertexNum = sc.nextInt();
            System.out.println("please input the graph:");
            for (int i=1; i<=vertexNum; i++) {
                for (int j=1; j<=vertexNum; j++) {
                    String theWeight = sc.next();
                    
                    if (!theWeight.equals("i") && i < j) {
                        Edge theEdge = new Edge();
                        
                        theEdge.startVertex = i;
                        theEdge.endVertex = j;
                        theEdge.weight = Integer.parseInt(theWeight);
                        allEdgeList.add(theEdge);
                    }
                }    
            }
        } finally {
            sc.close();
        }
        for (int i=1; i<=vertexNum; i++) {
            minSpanTree.put(i, new HashMap<Integer, Integer>());
            for (int j=1; j<=vertexNum; j++)
                minSpanTree.get(i).put(j, Integer.MAX_VALUE);
        }
        Collections.sort(allEdgeList);
        countEdge = 0;
        totalEdge = vertexNum - 1;
        while (countEdge != totalEdge) {
            Edge smallestEdge = allEdgeList.remove(0);
            
            if (!checkCycle(minSpanTree, vertexNum, smallestEdge.startVertex, smallestEdge.startVertex, smallestEdge.endVertex)) {
                minSpanTree.get(smallestEdge.startVertex).put(smallestEdge.endVertex, smallestEdge.weight);
                minSpanTree.get(smallestEdge.endVertex).put(smallestEdge.startVertex, smallestEdge.weight);
                countEdge++;
            }
        }
        System.out.println("the minimal spanning tree:");
        for (int i=1; i<=vertexNum; i++) {
            for (int j=1; j<=vertexNum; j++) {
                if (minSpanTree.get(i).get(j) == Integer.MAX_VALUE)
                    System.out.printf("%3s", "i");
                else
                    System.out.printf("%3d", minSpanTree.get(i).get(j));
            }
            System.out.println();
        }
    }
    
    private static boolean checkCycle(Map<Integer, Map<Integer, Integer>> minSpanTree, int vertexNum, int originalVertex, int preVertex, int nowVertex) {
        if (originalVertex == nowVertex)
            return true;
        else {
            for (int i=1; i<=vertexNum; i++) {
                if (minSpanTree.get(nowVertex).get(i) != Integer.MAX_VALUE && i != preVertex && checkCycle(minSpanTree, vertexNum, originalVertex, nowVertex, i))
                    return true;
            }
            return false;
        }
    }
}

範例輸入輸出:

抱歉沒空說明程式碼，只能說明一下輸入輸出的部份。首先輸入圖形上總共點的數量，再輸入相鄰矩陣，橫軸表示點1~點10，縱軸也是表示點1~點10，輸入的是點到點之間的權重，若輸入i表示這兩點不相連，也就是權重無限大。輸出結果也是相鄰矩陣，表示找到的最小成本擴展樹。本範例輸入是採用課本習題2的圖，所以可以參照課本的圖方便了解。

Prim's Algorithm

Java code:

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

class Edge {
    int startVertex, endVertex, weight;
}

class PriQueueComparator implements Comparator<Edge> {

    @Override
    public int compare(Edge thisEdge, Edge otherEdge) {
        if (thisEdge.weight < otherEdge.weight)
            return -1;
        else if (thisEdge.weight == otherEdge.weight)
            return 0;
        else
            return 1;
    }
}

public class PrimAlgorithm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertexNum;
        int nextVertex;
        Set<Integer> used = new HashSet<Integer>();
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<Integer, Map<Integer, Integer>>();
        Map<Integer, Map<Integer, Integer>> minSpanTree = new HashMap<Integer, Map<Integer, Integer>>();
        Queue<Edge> priQueue;
        
        try {
            System.out.print("please input the number of total vertexes:");
            vertexNum = sc.nextInt();
            priQueue = new PriorityQueue<Edge>(vertexNum - 1, new PriQueueComparator());
            System.out.println("please input the graph:");
            for (int i=1; i<=vertexNum; i++)
                graph.put(i, new HashMap<Integer, Integer>());
            for (int i=1; i<=vertexNum; i++) {
                for (int j=1; j<=vertexNum; j++) {
                    String input = sc.next();
                    
                    if (input.equals("i"))
                        graph.get(i).put(j, Integer.MAX_VALUE);
                    else
                        graph.get(i).put(j, Integer.parseInt(input));
                }
            }
        } finally {
            sc.close();
        }
        for (int i=1; i<=vertexNum; i++) {
            minSpanTree.put(i, new HashMap<Integer, Integer>());
            for (int j=1; j<=vertexNum; j++)
                minSpanTree.get(i).put(j, Integer.MAX_VALUE);
        }
        nextVertex = 1;
        while (true) {
            Edge smallestEdge;
            
            used.add(nextVertex);
            if (used.size() == vertexNum)
                break;
            for (int i=1; i<=vertexNum; i++) {
                Edge theEdge = new Edge();
                
                if (graph.get(nextVertex).get(i) != Integer.MAX_VALUE) {
                    theEdge.startVertex = nextVertex;
                    theEdge.endVertex = i;
                    theEdge.weight = graph.get(nextVertex).get(i);
                    priQueue.add(theEdge);
                }
            }
            while (true) {
                smallestEdge = priQueue.poll();
                if (!used.contains(smallestEdge.endVertex))
                    break;
            }
            minSpanTree.get(smallestEdge.startVertex).put(smallestEdge.endVertex, smallestEdge.weight);
            minSpanTree.get(smallestEdge.endVertex).put(smallestEdge.startVertex, smallestEdge.weight);
            nextVertex = smallestEdge.endVertex;
        }
        System.out.println("minimal spanning tree");
        for (int i=1; i<=vertexNum; i++) {
            for (int j=1; j<=vertexNum; j++) {
                if (minSpanTree.get(i).get(j) == Integer.MAX_VALUE)
                    System.out.printf("%3s", "i");
                else
                    System.out.printf("%3d", minSpanTree.get(i).get(j));
            }
            System.out.println();
        }
    }
}

範例輸入輸出:

2013年5月6日星期一

10156 - Sala-ma-Sond, A Nice Little Pond

The Problem

Of course, the turtles aren't completely free. In particular, they aren't free to swim where other turtles are swimming. To learn more about the swimming behaviour of turtles you decide to write a computer simulation of a pond and the turtles swimming in it.
For simplicity, you represent the pond as a rectangular grid, with turtles occupying positions at points on the grid. If the pond is an NxM grid, a position on the grid may be represented by a pair of integer coordinates (i, j), with 0 <= i < N and 0 <= j < M. The grid is aligned with its first dimension running north-south and its second dimension running east-west. Coordinate values increase to the south and the east.
A turtle swimming in the pond may be requested to move to the adjacent grid position in one of eight directions: N, S, E, W, NE, NW, SE, SW. If the request would cause the turtle to move off the grid or cause it to move onto a grid position occupied by another turtle, the request is ignored. Otherwise, the turtle happily obeys the movement request. (Turtles are easy to push around.)
The input consist of several data sets. Each data set begins with a description of the pond and the initial location of the turtles. The first line of the input consists of four integers separated by one or more spaces. The first integer specifies the size of the pond in the north-south direction (N), the second integer specifies the size of the pond in the east-west direction (M), the third integer specifies the number of turtles in the pond (T) and the fourth integer indicates the number of turtle movement requests (K). This first line is followed by T lines, each providing information on a single turtle. Each line of turtle information consists of three integers separated by one or more spaces. The first integer specifies a turtle id, the second integer specifies an initial grid position for the turtle along the north-south dimension, and the third integer specifies an initial grid position for the turtle along the east-west dimension. All turtles will be located at valid grid positions; no two turtles will be located at the same grid position; turtle ids are in the range one to ten thousand; the maximum size of the grid in either dimension is sixty; the minimum size is two.
Following the description of the pond and its initial turtle configuration, the remainder of the input, consists of a sequence of K turtle movement requests, one per line. Each movement request consists of a turtle id followed by a movement direction, and indicates that the specified turtle should be requested to move one grid position in the specified direction. The turtle id and movement direction are separated by one or more spaces. The movement direction is one of: `N', `S', `E', `W', `NE', `NW', `SE', `SW'. The turtle requests should be processed sequentially starting from the initial pond configuration given in the input.
The output is a graphical representation of the pond configuration for each data set after all turtle movement requests have been processed. A picture of the pond is rendered using ASCII characters. Beginning with the most northerly row, each row of the grid is represented by a single line in the output. Grid positions along a row are represented by character positions in the output line. The final position of a turtle is marked with an asterisk (`*'); space characters are used to fill empty grid positions. If the output is displayed as text on a computer screen or printed page, the result is a map of turtle positions in the pond, with north toward the top, east toward the right, and west toward the left. Spaces should be generated only when required for positioning turtles; output lines should not have trailing spaces. Print a blank line after each data set.

Sample Input

Sample Output

*

 *
   *

 *
*

   *

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1097

這一題基本上就是照著題目做就對了，不過要注意移動烏龜的時候不能超出池塘的範圍或是撞到別的烏龜(也就是兩個烏龜不能在同一個位置)，如果有以上違反規定的移動出現就要忽略。

以下是c++程式碼:

#include <iostream>
#include <map>
using namespace std;

typedef map<int, int> colMap;
struct position {
    int x, y;
};

int main() {
    int row, col, turNum, req;

    while (cin >> row >> col >> turNum >> req) {
        map<int, struct position> findTur;
        map<int, colMap> pool;
        map<int, int> rowMax;
        struct position pos[turNum];

        for (int i=0; i<turNum; i++) {
            int turId, x, y;

            cin >> turId >> x >> y;
            pos[i].x = x;
            pos[i].y = y;
            findTur[turId] = pos[i];
            pool[x][y] = turId;
        }
        for (int i=0; i<req; i++) {
            int turId, x, y;
            string dir;

            cin >> turId >> dir;
            x = findTur[turId].x;
            y = findTur[turId].y;
            pool[x][y] = 0;
            if (dir == "N")
                x--;
            else if (dir == "S")
                x++;
            else if (dir == "E")
                y++;
            else if (dir == "W")
                y--;
            else if (dir == "NE") {
                x--;
                y++;
            }
            else if (dir == "NW") {
                x--;
                y--;
            }
            else if (dir == "SE") {
                x++;
                y++;
            }
            else if (dir == "SW") {
                x++;
                y--;
            }
            if (x >= 0 && y >= 0 && x < row && y < col && pool[x][y] == 0) {
                findTur[turId].x = x;
                findTur[turId].y = y;
                pool[x][y] = turId;
            }
            else
                pool[findTur[turId].x][findTur[turId].y] = turId;
        }
        for (int i=0; i<row; i++) {
            int j;

            for (j=col-1; j>=0 && pool[i][j]==0; j--);
            rowMax[i] = j;
        }
        for (int i=0; i<row; i++) {
            for (int j=0; j<=rowMax[i]; j++) {
                if (pool[i][j])
                    cout << '*';
                else
                    cout << ' ';
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}

10101 - Bangla Numbers

Bangla numbers normally use 'kuti' (10000000), 'lakh' (100000), 'hajar' (1000), 'shata' (100) while expanding and converting to text. You are going to write a program to convert a given number to text with them.

Input

The input file may contain several test cases. Each case will contain a non-negative number <= 999999999999999.

Output

For each case of input, you have to output a line starting with the case number with four digits adjustment followed by the converted text.

Sample Input

23764
45897458973958

Sample Output

   1. 23 hajar 7 shata 64
   2. 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1042

這題就是把數字代進去遞迴求解即可。比較需要注意的是input數字可能會很大，所以我使用long long 資料型態，以及要考慮到input是0的情況，最後注意到output開頭的case數字格式是有特別規範的，需要4個格子並且靠右輸出。

以下是c++程式碼:

#include <iostream>
#include <iomanip>
using namespace std;

void bangla(long long num) {
    if (num >= 10000000) {
        bangla(num / 10000000);
        cout << " kuti";
        num %= 10000000;
    }
    if (num >= 100000) {
        bangla(num / 100000);
        cout << " lakh";
        num %= 100000;
    }
    if (num >= 1000) {
        bangla(num / 1000);
        cout << " hajar";
        num %= 1000;
    }
    if (num >= 100) {
        bangla(num / 100);
        cout << " shata";
        num %= 100;
    }
    if (num)
        cout << " " << num;
}

int main() {
    long long num;
    long long countCase = 0;

    while (cin >> num) {
        cout << setw(4) << right << ++countCase << ".";
        if (num)
            bangla(num);
        else
            cout << " 0";
        cout << endl;
    }

    return 0;
}

訂閱：文章 (Atom)

2013年6月3日 星期一

2013年5月10日 星期五

2013年5月9日 星期四

2013年5月6日 星期一

The Problem

Sample Input

Sample Output

2013年6月3日星期一

2013年5月10日星期五

2013年5月9日星期四

2013年5月6日星期一