【POJ】Highways

Problem here

Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.

Input

The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.

Output

For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

Sample Input

1

3
0 990 692
990 0 179
692 179 0

Sample Output

692

Hint

Huge input,scanf is recommended.

Source

POJ Contest,Author:Mathematica@ZSU

Solution

#include <string>
#include <cstdio>
#include <stdio.h>
#define MAX_NUM 0x3f3f3f3f
using namespace std;
int map[501][501];
int dis[501];
bool visit[501];
int n, cnt, min_num, j, sum;
void prim(){
    while(cnt < n){
        min_num = MAX_NUM;
        for(int i = 1; i <=  n; i++){
            if(visit[i] == false && dis[i] < min_num){
                min_num = dis[i];
                j = i;
            }
        }
        visit[j] = true;
        cnt++;
        sum = max(sum, dis[j]);
        for(int i = 1; i <= n; i++){
            if(visit[i] == false && dis[i] > map[j][i]){
                dis[i] = map[j][i];
            }
        }
    }
}

int main(){

    int kase;
    scanf("%d", &kase);
    while(kase--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d", &map[i][j]);
            }
        }
        for(int i = 2; i <= n; i++){
            dis[i] = map[1][i];
            visit[i] = false;
        }

        sum = 0;
        visit[1] = true;
        dis[1] = 0;
        cnt = 1;
        prim();
        printf("%d\n", sum);
    }

    return 0;
}

【HDU】Red and Black

Problem here

Problem Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.'.' - a black tile '#' - a red tile '@' - a man on a black tile(appears exactly once in a data set)

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

Sample Output
45

Source

Asia 2004, Ehime (Japan), Japan Domestic

Solution

#include <iostream>
#include <memory.h>
using namespace std;
int w, h;
int map[100][100];
int cnt;

void dfs(int x, int y){
    if(x < 0 || y < 0 || x >= h || y >= w || map[x][y] == 1)
        return;

    cnt++;
    map[x][y] = 1;
    dfs(x+1, y);
    dfs(x, y+1);
    dfs(x-1, y);
    dfs(x, y-1);
}

int main(){
    while(cin >> w >> h){
        if(w == 0 && h == 0)
            break;

        int p, q;
        cnt = 0;
        memset(map, 0, sizeof(map));
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                char input;
                cin >> input;
                if(input == '@'){
                    p = i; 
                    q = j;
                }
                if(input == '#')
                    map[i][j] = 1;

            }
        }

        dfs(p, q);
        cout << cnt << endl;
    }

    return 0;
}

【POJ】A Knight's Journey

Problem here

Description

Background

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? *Problem** Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p q <= 26. This represents a p q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number. If no such path exist, you should output impossible on a single line.

Sample Input

31 12 34 3

Sample Output

Scenario #1:A
1Scenario #2:impossible
Scenario #3:A1B3C1A2B4C2A3B1C3A4B2C4

Source

TUD Programming Contest 2005, Darmstadt, Germany

Solution

#include <iostream>
#include <memory.h>
using namespace std;

int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

int allStep;
char ans[100];
bool visit[100][100];
bool ok;
int p, q;

void dfs(int cnt, int x, int y){
    if(cnt == allStep){
        for(int i = 0; i < 2*cnt; i++){
            cout << ans[i];
        }
        cout << endl;
        ok = true;
        return ;
    }

    for(int i = 0; i < 8; i++){
        if(ok == false){
            int new_x = x+dx[i];
            int new_y = y+dy[i];
            if(new_x > 0 && new_y > 0 && new_x <= q && new_y <= p){
                if(visit[new_x][new_y] == false){
                    visit[new_x][new_y] = true;
                    ans[2*cnt] = 'A' + new_x-1;
                    ans[2*cnt+1] = '1' + new_y-1;
                    dfs(cnt+1, new_x, new_y);
                    visit[new_x][new_y] = false;
                }
            }
        }
    }
}

int main(){

    int kase;
    cin >> kase;
    for(int ks = 1; ks <= kase; ks++){
        cin >> p >> q;
        allStep = p*q;
        memset(visit, false, sizeof(visit));
        ok = false;
        visit[1][1] = true;
        ans[0] = 'A';
        ans[1] = '1';
        cout << "Scenario #" << ks << ":" << endl;
        dfs(1, 1, 1);
        if(ok == false){
            cout << "impossible" << endl;
        }
        cout << endl; 
    }

    return 0;
}

【UVa】208 - Firetruck

Problem here

Problem

The Center City fire department collaborates with the transportation department to maintain maps
of the city which reflects the current status of the city streets. On any given day, several streets are
closed for repairs or construction. Firefighters need to be able to select routes from the firestations to
fires that do not use closed streets.
Central City is divided into non-overlapping fire districts, each containing a single firestation. When
a fire is reported, a central dispatcher alerts the firestation of the district where the fire is located and
gives a list of possible routes from the firestation to the fire. You must write a program that the central
dispatcher can use to generate routes from the district firestations to the fires.

INPUT

The city has a separate map for each fire district. Streetcorners of each map are identified by positive
integers less than 21, with the firestation always on corner #1. The input file contains several test cases
representing different fires in different districts.
• The first line of a test case consists of a single integer which is the number of the streetcorner
closest to the fire.
• The next several lines consist of pairs of positive integers separated by blanks which are the
adjacent streetcorners of open streets. (For example, if the pair 4 7 is on a line in the file, then
the street between streetcorners 4 and 7 is open. There are no other streetcorners between 4 and
7 on that section of the street.)
• The final line of each test case consists of a pair of 0’s.

OUTPUT

For each test case, your output must identify the case by number (‘CASE 1:’, ‘CASE 2:’, etc). It must
list each route on a separate line, with the streetcorners written in the order in which they appear on
the route. And it must give the total number routes from firestation to the fire. Include only routes
which do not pass through any streetcorner more than once. (For obvious reasons, the fire
department doesn’t want its trucks driving around in circles.)
Output from separate cases must appear on separate lines.

Sample

input

6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0

output

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

Solution

Floyd 判斷b能否到達終點
再判斷a 能否到達b

#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int a[30][30], b[30][30];
int visit[30], ans[30];
int m, cas, cnt, n;

void dfs(int c, int p){
    if(p == n){
        cnt++;
        for(int i = 0; i < c; i++){
            if(i > 0)   
                cout << " ";
            cout << ans[i];
        }
        cout << endl;
        return ;
    }

    for(int i = 1; i <= m; i++){
        if(visit[i])
            continue;
        if(!a[p][i])
            continue;
        if(!b[i][n])
            continue;
        visit[i] = 1;
        ans[c] = i;
        dfs(c+1,i);
        visit[i] = 0;
    }
}

int main(){
    cas = 0;
    while(cin >> n){
        int x, y;
        cas++;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(visit, 0, sizeof(visit));
        memset(ans, 0, sizeof(ans));
        while(cin >> x >> y){
            if(x == 0 && y == 0)
                break;

            a[x][y] = a[y][x] = 1;
            b[x][y] = b[y][x] = 1;
            m = max(m, max(x, y));
        }

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= m; j++)
                for(int k = 1; k <= m; k++)
                    if(b[j][i] && b[i][k])
                        b[j][k] = 1;

        cnt = 0;
        visit[1] = 1;
        ans[0] = 1;
        cout << "CASE " << cas << ":" << endl;
        dfs(1, 1);
        cout << "There are " << cnt << " routes from the firestation to streetcorner " << n << "." << endl;

    }

    return 0;
}