uva 10067 - Playing with Wheels

Problem C

Playing with Wheels

Input: standard Input

Output: standard output

In this problem we will be considering a game played with four wheels. Digits ranging from 0 to 9 are printed consecutively (clockwise) on the periphery of each wheel. The topmost digits of the wheels form a four-digit integer. For example, in the following figure the wheels form the integer 8056. Each wheel has two buttons associated with it. Pressing the button marked with a left arrow rotates the wheel one digit in the clockwise direction and pressing the one marked with the right arrow rotates it by one digit in the opposite direction.

                

The game starts with an initial configuration of the wheels. Say, in the initial configuration the topmost digits form the integer S₁S₂S₃S₄. You will be given some (say, n) forbidden configurations F_i1F_i2F_i3F_i4  (1 <= i <= n ) and a target configuration T₁T₂T₃T₄. Your job will be to write a program that can calculate the minimum number of button presses required to transform the initial configuration to the target configuration by never passing through a forbidden one.

Input

The first line of the input contains an integer N giving the number of test cases to follow.

The first line of each test case contains the initial configuration of the wheels specified by 4 digits. Two consecutive digits are separated by a space. The next line contains the target configuration. The third line contains an integer n giving the number of forbidden configurations. Each of the following n lines contains a forbidden configuration.

There is a blank line between two consecutive input sets.

           

Output

For each test case in the input print a line containing the minimum number of button presses required. If the target configuration is not reachable then print -1.

Sample Input

2
8 0 5 6
6 5 0 8
5
8 0 5 7
8 0 4 7
5 5 0 8
7 5 0 8
6 4 0 8

0 0 0 0
5 3 1 7
8
0 0 0 1
0 0 0 9
0 0 1 0
0 0 9 0
0 1 0 0
0 9 0 0
1 0 0 0
9 0 0 0

Sample Output

14
-1

______________________________________________________________________________________
Rezaul Alam Chowdhury

BFS

#include<stdio.h>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

bool trav[10000];
int start[4],csn[4],end;
set<int>forbid;
void getCN(int a){
    int i=3;
    memset(csn,0,sizeof(csn));
    while(a>0)csn[i--]=a%10,a/=10;
}
int getN(){
    return csn[0]*1000+csn[1]*100+csn[2]*10+csn[3];
}
void ans(){
    memcpy(csn,start,sizeof(start));
    memset(trav,0,sizeof(trav));
    queue<pair<int,int> >q;
    int cur,res=-1,dis,b,next;
    cur=getN();
    trav[cur]=1;
    q.push(make_pair(cur,0));
    while(q.size()){
        cur=q.front().first,dis=q.front().second;q.pop();
        if(DBG)printf("cur dis %d %d\n",cur,dis);
        if(cur==end){res=dis;break;}
        getCN(cur);
        rep(i,4){
            b=csn[i],csn[i]=(csn[i]+1)%10;
            next=getN();
            if(!trav[next]&&!forbid.count(next))trav[next]=1,q.push(make_pair(next,dis+1));
            csn[i]=b,csn[i]=((csn[i]-1)<0?9:(csn[i]-1));
            next=getN();
            if(!trav[next]&&!forbid.count(next))trav[next]=1,q.push(make_pair(next,dis+1));
            csn[i]=b;
        }
    }
    printf("%d\n",res);
}
int main(){
    int n,a,b,c,d,e;
    scanf("%d",&n);
    rep(i,n){
        forbid.clear();
        scanf("%d%d%d%d",&start[0],&start[1],&start[2],&start[3]);
        scanf("%d%d%d%d",&a,&b,&c,&d),end=a*1000+b*100+c*10+d;
        scanf("%d",&a);
        rep(i,a){
            scanf("%d%d%d%d",&b,&c,&d,&e);
            forbid.insert(b*1000+c*100+d*10+e);
        }
        ans();
    }
}

uva 439 - Knight Moves

Knight Moves

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input Specification

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output Specification

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

BFS

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int R1,C1,R2,C2;
string S1,S2;
bool visit[8][8];
int pad[8][2];
struct Node{
    Node(int a,int b,int c):r(a),c(b),dis(c){}
    int r,c,dis;
};
void init(){
    pad[0][0]=-1,pad[0][1]=-2,
    pad[1][0]=-1,pad[1][1]=2,
    pad[2][0]=1,pad[2][1]=2,
    pad[3][0]=1,pad[3][1]=-2,
    pad[4][0]=-2,pad[4][1]=-1,
    pad[5][0]=-2,pad[5][1]=1,
    pad[6][0]=2,pad[6][1]=1,
    pad[7][0]=2,pad[7][1]=-1;
}
bool valid(int a,int b){
    return a>=0&&b>=0&&a<8&&b<8;
}
void getNum(){
    int ans=0;
    bool f=0;
    memset(visit,0,sizeof(visit));
    queue<Node>q;
    q.push(Node(R1,C1,0));
    if(!(R1==R2&&C1==C2))
        while(q.size()){
            int x=q.front().r,y=q.front().c,dis=q.front().dis;
            q.pop();
            visit[x][y]=1;
            if(DBG)printf("x y dis %d %d %d\n",x,y,dis);
            rep(i,8){
                int c=x+pad[i][0],d=y+pad[i][1];
                if(valid(c,d)&&!visit[c][d]){
                    if(c==R2&&d==C2){ans=dis+1,f=1;break;}
                    q.push(Node(c,d,dis+1));
                }
            }
            if(f)break;
        }
    printf("To get from %s to %s takes %d knight moves.\n",S1.c_str(),S2.c_str(),ans);
}
int main(){
    init();
    while(cin>>S1>>S2){
        R1=(S1[1]-'1'),C1=S1[0]-'a';
        R2=(S2[1]-'1'),C2=S2[0]-'a';
        if(DBG)printf("%d %d %d %d\n",R1,C1,R2,C2);
        getNum();
    }
}

uva 10010 - Where's Waldorf?

Where's Waldorf?

Given a m by n grid of letters, ( ), and a list of words, find the location in the grid at which the word can be found. A word matches a straight, uninterrupted line of letters in the grid. A word can match the letters in the grid regardless of case (i.e. upper and lower case letters are to be treated as the same). The matching can be done in any of the eight directions either horizontally, vertically or diagonally through the grid.

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input begins with a pair of integers, m followed by n,  in decimal notation on a single line. The next m lines contain n letters each; this is the grid of letters in which the words of the list must be found. The letters in the grid may be in upper or lower case. Following the grid of letters, another integer k appears on a line by itself ( ). The next k lines of input contain the list of words to search for, one word per line. These words may contain upper and lower case letters only (no spaces, hyphens or other non-alphabetic characters).

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
For each word in the word list, a pair of integers representing the location of the corresponding word in the grid must be output. The integers must be separated by a single space. The first integer is the line in the grid where the first letter of the given word can be found (1 represents the topmost line in the grid, and m represents the bottommost line). The second integer is the column in the grid where the first letter of the given word can be found (1 represents the leftmost column in the grid, and n represents the rightmost column in the grid). If a word can be found more than once in the grid, then the location which is output should correspond to the uppermost occurence of the word (i.e. the occurence which places the first letter of the word closest to the top of the grid). If two or more words are uppermost, the output should correspond to the leftmost of these occurences. All words can be found at least once in the grid.

Sample Input 

1

8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
4
Waldorf
Bambi
Betty
Dagbert

Sample Output 

2 5
2 3
1 2
7 8

---

Miguel Revilla
2000-08-22

BFS

uva 10004 - Bicoloring

Bicoloring

In 1976 the ``Four Color Map Theorem" was proven with the assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume:

• no node will have an edge to itself.
• the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
• the graph will be strongly connected. That is, there will be at least one path from any node to any other node.

Input 

The input consists of several test cases. Each test case starts with a line containing the number n ( 1 < n < 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a ( ).An input with n = 0 will mark the end of the input and is not to be processed.

Output 

You have to decide whether the input graph can be bicolored or not, and print it as shown below.

Sample Input 

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

Sample Output 

NOT BICOLORABLE.
BICOLORABLE.

---

Miguel Revilla
2000-08-21

BFS 

uva 677 - All Walks of length "n" from the first node

All Walks of length n from the first node

A computer network can be represented as a graph. Let G = (V, E) be an undirected graph, V = represents all nodes, where m is the number of nodes, and E represents all edges. The first node is v₁ and the last node is v_m . The number of edges is k. Define the adjacency matrix where 

An example of the adjacency matrix and its corresponding graph are as follows:

 

Calculate 

and use the Boolean operations where 0+0 = 0, 0+1=1+0=1, 1+1=1, and . The entry in row i and column j of A_n is 1 if and only if at least there exists a walk of length n between the i-th and j-th nodes of V. In other words, the distinct walks of length n between the i-th and j-th nodes of V may be more than one. Note that the node in the paths can be repetitive.

The following example shows the walks of length 2. 

Write programs to do above calculation and print out all distinct walks of length n. (In this problem we let the maximum walks of length n be 5 and the maximum number of nodes be 10.)

Input 

The input file contains a number of test examples, the test examples are separated by -9999. Each test example consists of the number of nodes and the length of walks in the first row, and then the adjacency matrix.

Output 

The output file must contain all distinct walks of the length n, and with all its nodes different, from the first node, listed in lexicographical order. In case there are not walks of length n, just print `no walk of length n'

Separate the output of the different cases by a blank line.

Sample Input 

5 2
0 1 0 1 0
1 0 1 0 0
0 1 0 1 1
1 0 1 0 1
0 0 1 1 0
-9999
5 3
0 1 0 1 0
1 0 1 0 0
0 1 0 1 1
1 0 1 0 1
0 0 1 1 0

Sample Output 

(1,2,3)
(1,4,3)
(1,4,5)

(1,2,3,4)
(1,2,3,5)
(1,4,3,2)
(1,4,3,5)
(1,4,5,3)

---

Miguel Revilla
2000-08-14

BFS on graph

uva 614- Mapping the Route

Mapping the Route

Finding a path through a maze is a popular problem for computers. In this problem, a maze will consist of a rectangular array of square cells, each of which may have walls on the north, south, east and/or west sides of the cell. One cell will be identified as the starting point, and another will be identified as the goal. Your task is to find the unique route from the starting point to the goal, label each cell in the path with its sequence in the path, identify the cells that were visited but that were not in the path, and display the maze.


The algorithm you use to find a path through the maze must be the one described below. Imagine a robot is positioned in the starting cell. The robot first attempts to go west from that cell, then north, then east, then south, in sequence. The robot can move in the selected direction if

(a)

there is no wall preventing it from moving in that direction, and

(b)

it has not yet been in the next cell in that direction.

When the robot reaches the goal, its trip is over. If the robot reaches a cell at which no further progress is possible, it retreats to the previous cell it occupied and attempts to move in the next untried direction.


Consider the simple maze shown on the left below. It is two cells high and three cells wide. The starting cell is labeled `S' and the goal cell is labeled `G'. When the robot starts, it would first try to move west (left), but finds a wall. It then tries to move north (up), and is again blocked by a wall. A wall also prevents it from moving east (right), so it finally tries to move south (down), and succeeds. From the new cell it will eventually move east. Here it repeats its movement algorithm. Although no wall blocks its potential westward movement, it has already 'visited' the cell in that direction, so it next tries to move north, and is successful. Unfortunately, after moving north, it finds no way to extend its path, and so it retreats to the previously occupied cell. Now it tries to move east, and is successful. From that cell it will move north, and there it finds the goal. The maze that would be displayed on the output is shown on the right below. Note that the starting cell is labeled `1', each cell in the path to the goal (including the one containing the goal) is labeled with its sequence number, and each cell that was visited but is not in the path is labeled with question marks.

                     +---+---+---+        +---+---+---+
                     | S |   | G |        |  1|???|  5|
                     +   +   +   +        +   +   +   +
                     |           |        |  2   3   4|
                     +---+---+---+        +---+---+---+

Input 

View the maze as an array of cells, with the northernmost row being row 1, and the westernmost column being column 1. In the maze above, the starting cell is row 1, column 1, and the goal cell is row 1, column 3.

There will be one or more mazes to process in the input. For each maze there will first appear six integers. The first two give the height (number of rows) and width (numer of columns) of the maze (in cells). The next two give the position (row and column number) of the starting cell, and the last two give the position of the goal. No maze will have more than 12 rows or 12 columns, and there will always be a path from the starting point to the goal.


Following the first six integers there will appear one integer for each cell, in row major order. The value of each integer indicates whether a cell has a wall on its eastern side (1) and whether it has a wall on its southern side (2). For example, a cell with no eastern or southern wall has a value of 0. A cell with only a southern wall has a value of 2. A cell with both an eastern and a southern wall has a value of 3. The cells on the periphery of the maze always have appropriate walls to prevent the robot from leaving the maze; these are not specified in the input data.


The last maze in the input data will be followed by six zeroes.

Output 

For each maze, display the maze as shown in the example above and the expected output below, appropriately labeled and prefixed by the maze number. The mazes are numbered sequentially starting with 1. Print two blank lines after each dataset.

Sample Input 

2 3 1 1 1 3
1 1 0
0 0 0

4 3 3 2 4 3
0 3 0
0 2 0
0 3 0
0 1 0

0 0 0 0 0 0

Sample Output 

Maze 1

+---+---+---+
|  1|???|  5|
+   +   +   +
|  2   3   4|
+---+---+---+


Maze 2

+---+---+---+
|??? ???|???|
+   +---+   +
|  3   4   5|
+   +---+   +
|  2   1|  6|
+   +---+   +
|       |  7|
+---+---+---+

---

Miguel A. Revilla
1999-03-24

BFS + output