lab exam ds

The square field consists of M ∗ M cells. Each cell is colored in one of three colors (1,2,3). The initial state
is chosen in one of the cells of color 1. In each step one allowed to move one cell up, down, left or right
remaining inside the field.
You are to define the minimal amount of steps one should make to get a cell of color 3 independent on the
initial state. NOTE: this means you could be starting at any of the 1.
Also note that the field contains at least one cell of color 1 and at least one cell of color 3.
1.1
Input Format
The input consists of several input blocks. The first line of each block contains integer M, the size of the
field. Then there are M lines with colors of the cells.
1.2
Output Format
For each input block the output should consist of one line with the integer, the minimal amount of steps one
should make to get a cell of color 3 independent on the initial state.
1.3
Sample Input
4
1223
2123
2213
3212
2
12
33
1.4
Sample Output
3
1


Program:


#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct node
{
    int n;
    char v;
    struct node*next;
}node;
int main(void)
{
    char val[10005];
    int t,i,m,j,k,in[10005];
    node* a[10005],*tmp;
    char d,c='a';
    m=0;
    while((c=getchar())!=EOF)//scan char by char till EOF
    {
    while(c>='0'&&c<='9')//find m
    {
        m=m*10+c-'0';
        c=getchar();
    }
    k=0;
    for(i=0;i<m*m;i++)//scan the matrix
    {
        scanf("%c",&val[i]);//store the values in val array
        a[i]=NULL;//set ith node to NULL
        if(val[i]=='1')//store indices of all 1's in in array
        in[k++]=i;
        if(((i+1)%m)==0)//scan \n
        d=getchar();
    }
    c=d;
    for(i=0;i<m*m;i++)// create linked lists for adjacency list representation of matrix as a graph
    {
        if(i%m!=0)
        {
        tmp=a[i];
        a[i]=malloc(sizeof(node));
        a[i]->n=i-1;
        a[i]->v=val[i-1];
        a[i]->next=tmp;
        }
        if(i+1<m*m&&(i+1)%m!=0)
        {
        tmp=a[i];
        a[i]=malloc(sizeof(node));
        a[i]->n=i+1;
        a[i]->v=val[i+1];
        a[i]->next=tmp;
        }
        if(i-m>=0)
        {
        tmp=a[i];
        a[i]=malloc(sizeof(node));
        a[i]->n=i-m;
        a[i]->v=val[i-m];
        a[i]->next=tmp;
        }
        if(i+m<m*m)
        {
        tmp=a[i];
        a[i]=malloc(sizeof(node));
        a[i]->n=i+m;
        a[i]->v=val[i+m];
        a[i]->next=tmp;
        }
    }
      int min=0;
    for(i=0;i<k;i++)//find minimum distance b/w each '1' and a '3' and find the maximum of these minimum distances
    {
        int d[10005],flag;
        for(j=0;j<m*m;j++)
        d[j]=INT_MAX;
        int f=0,r=0,vis[10005]={0},queue[10005];
        queue[r++]=in[i];
        d[in[i]]=0;
        vis[in[i]]=1;
        flag=0;
        while(flag==0&&f!=r)
        {
        t=queue[f++];
        for(tmp=a[t];tmp!=NULL;tmp=tmp->next)
        {
            vis[tmp->n]=1;
            d[tmp->n]=d[t]+1;
            queue[r++]=tmp->n;
            if(tmp->v=='3')
            {
            flag=1;
            if(d[tmp->n]>min)
                min=d[tmp->n];
            }
        }
        }
    }
    printf("%d\n",min);
    m=0;
    }
    return 0;
}

12376 - As Long as I Learn, I Live Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3798

What makes problem solving so interesting? What makes it challenging? Why we put so much effort on it but never get bored? For us (problem-setters), it's like 'As long as I learn, I live!' We learn so many beautiful things, we find great ideas and techniques and there is no end to it.

In this problem, you are given a person's life stages in graph form. There are n nodes in the graph. Nodes represent stages, numbered from 0 to n-1, and edges represents that he can move from one stage to another. 0^th node is the node where he starts his journey. You may have guessed; there will be no cycles in the graph (no one can back to past!).

In each node, a value x is attached, it means he will learn x units, if he comes into this node. For example, the graph in the picture represents a person's life stages. The circles present nodes, the value in a circle represents that it will be gained if the person comes into this node. The numbers in rectangular boxes represents the node ids. If the person reaches the 1^st node he will learn 8 added units, if he reaches 4^th node, he will learn 7 added units.

As in real life, no one knows the future, but can predict some common things in near future. If the person is in node u, he only knows the nodes that have an edge from u. The person wants to learn more, that's why, he always takes the stage that looks better, i.e. has maximum value. So, if he is in node 0, he only knows the learning units in node 1 and 2, but doesn't know about nodes 3, 4, or 5. He will prefer node 2 over node 1 (because node 2 will give him 9 learning units). He continues journey in this method. He can finish at any stage, but will try to learn more. You can assume that the graph is given such that from any node, the next node can be picked deterministically i.e. from any node u, there will be exactly one node v which has the maximum value and there is an edge from u to v.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers n (2 ≤ n ≤ 100) and m (n-1 ≤ m ≤ n*(n-1)/2), n denotes the number of nodes in the graph and m denotes the number of edges in the graph. The next line contains n space separated integers denoting the learning units in the nodes respectively. The values will be between 1 and 1000 (inclusive) except the 0^th node will have a value 0. Each of the next m lines contains two integers u v (0 ≤ u, v < n, u ≠ v) meaning that there is a directed edge from u to v. You can safely assume that the given graph will follow the restrictions described above. And from 0^th node, it can be possible to go to any node. There will be at most one edge between any pair of nodes.

Output

For each case, print the case number and the maximum total learning units the person can gain (following the strategy mentioned above) and the node id where the person ends journey.

 Algorithm:

 Graph BFS or DFS problem

This problem you can solve using recursive method, or you can use BFS or DFS for solve this problem.

The recursive method is best solution for solve this problem.

This method is

store all learning unit to LU[100]

total_learning_unit=LU[0];

run findAns(0);

void findAns(int u)

----if u has no adjacency node then set ans_node=u and return //i.e. break find ans

----find the max learning unit from all node which are adjacency of u. suppose the max learning unit node is v.

----total_learning_unit += LU[v];

----findAns(v);

print total_learning_unit and ans_node

Program:

#include<stdio.h>
struct list
{
    int b[100];
    int k;
};
int main()
{
    struct list a[105];
    int j,f,s,o,l,i,u,v,c[105],t,n,m,z;
    scanf("%d",&t);
    char d;
    for(o=1;o<=t;o++)
    {
    scanf("%c%d%d",&d,&n,&m);
    for(i=0;i<n;i++)
    {
        a[i].k=0;
        scanf("%d",&c[i]);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        a[u].b[a[u].k++]=v;
    }
    s=0;
    l=0;
    while(1)
    {
        m=0;
        if(a[s].k==0)
        break;
        for(i=0;i<a[s].k;i++)
        {
        if(c[a[s].b[i]]>m)
        {
            m=c[a[s].b[i]];
            z=a[s].b[i];
        }
        }
        l+=m;
        s=z;
    }
    printf("Case %d: %d %d\n",o,l,s);
    }
    return 0;
}

 

Sample Input                              Output for Sample Input

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

Case 1: 29 4