11878 – Homework Checker UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3000

A really easy problem. Input parsing, linear scan

How I did it

• I Read the lines until I find an EOF .
• Parse every line with 2 flags. Flag 1 until I get ‘+’ or ‘-‘. Flag 2 until i found ‘=’. Flag 3 the rest of the string.
• Parse number 1, number 2 and answer.
• If the equation is ok, correct answer +1.
• Print the number of correct answers.

Hints

• Just read until EOF.

Code

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

int parseInt(string number)
{
    int num;
    for(int x=0; x<number.size(); x++)
    {
        if(x == 0)
           num = number[x] - '0';
        else
            num = (num * 10) + (number[x] - '0');
    }
    return num;
}

int main()
{
char sign;
string str;
bool flag1, flag2;
string n1, n2, res;
int tot = 0;

while(cin>>str)
{
    flag1 = flag2 = false;
    n1 = n2 = res = "";

    for(int a=0; a<str.size(); a++)
    {
        if(isdigit(str[a]) || str[a] == '?')
        {
            if(!flag1)
               n1 += str[a];
            else if(!flag2)
                    n2 += str[a];
            else
                res += str[a];
        }
        else if(str[a] == '+' || str[a] == '-')
        {
            sign = str[a];
            flag1 = true;
        }
        else
        {
            flag2 = true;
        }
    }

    if(res != "?")
    {
        int number1 = parseInt(n1);
        int number2 = parseInt(n2);
        int answer  = parseInt(res);

        if(sign == '+')
        {
            if(number1 + number2 == answer)
              tot++;
        }
        else
        {
            if(number1 - number2 == answer)
              tot++;
        }
    }
}
printf("%d\n",tot);
return 0;
}

11518 – Dominos 2 UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2513

A really easy problem,  DFS, BFS.

How I did it

• Read the number of cases
• Read the number of dominos, edges, hand down.
• Init the graph.
• Read the vertex as a DAG.
• Call dfs with every hand down.
• Print the down elements.

Hints

• The graph can be represented as a DAG.

Critical Input

2
0 0 0
3 2 2
1 2
2 3
2
2
Critical Output
0
2
Code

#include <iostream>
#include <cstdio>
#include <vector>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
using namespace std;
typedef vector<int> vi;

vector<vi> graph;
vi dfs_num;
int tot;

void readGraph(int edges)
{
    int vertex1, vertex2;
    for(int x=1; x<=edges; x++)
    {
        scanf("%d %d", &vertex1, &vertex2);
        graph[vertex1 - 1].push_back(vertex2 - 1);
    }
}

void dfs(int node)
{
    if(dfs_num[node] == DFS_WHITE)
        tot++;
    dfs_num[node] = DFS_BLACK;

    for(int a=0; a<graph[node].size(); a++)
        if(dfs_num[graph[node][a]] == DFS_WHITE)

            dfs(graph[node][a]);

}

int main()
{
int casos, dominos, edges, down, piece;
scanf("%d", &casos);
while(casos--)
{
    scanf("%d %d %d", &dominos, &edges, &down);    tot = 0;
    graph.assign(dominos, vi());
    dfs_num.assign(dominos, DFS_WHITE);
    readGraph(edges);
    for(int x=1; x<=down; x++)
    {
        scanf("%d", &piece);
        dfs(piece - 1);
    }
    printf("%d\n", tot);
}
return 0;
}

11221 – Magic square palindromes.

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2162

A really easy problem, Ad hoc, palindromes.

How I did it

• Read the number of cases
• Read the string case.
• Insert into a string all the characters of the input string.
• If the root of the string size has decimals print no magic.
• Otherwise check if the 4 posible ways of set the string. If all re equals print the root, otherwise no magic.

Hints

• Cafeful with case.

Critical Input

3
sator arepo tenet opera rotas
sator arepo tenet opera rotaS
f

Critical Output
Case #1:
5
Case #2
No magic :(
Case #3
1

Code

Code

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
#define  MAX 102
using namespace std;

char matriz[MAX][MAX];
int main()
{
string cad, output;
int casos;

scanf("%d", &casos);
getline(cin,cad);//trash

for(int x=1; x<=casos; x++)
{
    output = "";
    getline(cin,cad);
    for(int y=0; y<cad.size(); y++)
        if(isalpha(cad[y]))
           output+=cad[y];
    printf("Case #%d:\n", x);

    double fSqrt  = sqrt(output.size());
    int    iSqrt = int(fSqrt);

    if(fSqrt - iSqrt != 0.0)
       printf("No magic 😦\n");
    else
    {
        int index = 0;
        for(int a=0; a < iSqrt; a++)
            for(int b=0; b < iSqrt; b++, index++)
                matriz[a][b] = output[index];

        string tmpWord = "";
        for(int a=0; a < iSqrt; a++)
            for(int b=0; b < iSqrt; b++)
                tmpWord += matriz[b][a];
        if(tmpWord != output)
           printf("No magic 😦\n");
        else
        {
            string tmpWord = "";
            for(int a=iSqrt-1; a >= 0; a--)
                for(int b=iSqrt-1; b >= 0; b--)
                    tmpWord += matriz[a][b];
            if(tmpWord != output)
               printf("No magic 😦\n");
            else
            {
                string tmpWord = "";
                for(int a=iSqrt-1; a >= 0; a--)
                    for(int b=iSqrt-1; b >= 0; b--)
                        tmpWord += matriz[b][a];
                if(tmpWord != output)
                   printf("No magic 😦\n");
                else
                    printf("%d\n", iSqrt);
            }
        }

    }
}
return 0;
}

11309 – Counting Chaos UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2284

A really easy problem, Ad hoc, palindromes.

How I did it

• Read the number of cases
• Read the hour and minutes.
• While the current hour is not palindrome increment the minutes an hours.
• If the hour is palindrome break the loop.
• Print hour and minute.

Hints

• Ignore all leading zeroes in HH.
• If HH is zero then ignore all leading zeroes in MM.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool isPal(int h, int m)
{
    vector<int> vec, tmp, vec2 ;
    if(h == 0)
    {
        if(m < 10)
          return true;
        else
        {
            while(m != 0)
            {
                vec.push_back(m%10);
                m/=10;
            }
            tmp = vec;
            reverse(vec.begin(), vec.end());
            if(vec == tmp)
               return true;
            else
                return false;
        }
    }
    else
    {
        while(h != 0)
        {
            vec.push_back(h % 10);
            h/=10;
        }
        reverse(vec.begin(), vec.end());

        if(m<10)
           vec.push_back(0);
        while(m != 0)
        {
            vec2.push_back(m % 10);
            m/=10;
        }
        reverse(vec2.begin(), vec2.end());

        vec.insert(vec.end(), vec2.begin(), vec2.end());
        tmp = vec;
        reverse(vec.begin(), vec.end());
        if(vec == tmp)
           return true;
        else
            return false;
    }
}

int main()
{
int casos, hh, mm;
bool flag = 0;
scanf("%d", &casos);
while(casos--)
{
    scanf("%d:%d", &hh, &mm);
    flag = false;

    while(flag != 1)
    {
        mm++;
        if(mm == 60)
        {
            mm = 0;
            hh++;
            if(hh == 24)
               hh = 0;
        }
        if(isPal(hh,mm))
        {
            flag = true;
            if(hh < 10)
               printf("0");
            printf("%d:", hh);
            if(mm<10)
               printf("0");
            printf("%d\n", mm);
        }
    }
}
return 0;
}

871 – Counting Cells in a Blob UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=812

A really easy problem using DFS. Flood fill.

How I did it

• Read the number of cases
• Read the element rows of the matrix.
• If I found the number 1, I set the dfs_matriz with -1.
• Traverse all the graph.
• If I found a unvisited node, I call dfs and increase the area size.
• Get the max area size.
• After the graph traversal print the max area

Hints

• Print a blank line between cases.
• The last case has not a blank line after having processed. If(cases != 0) print a blank line.

Critical Input

5

11000
01100
00101
10001
01011

11000
01100
00101
10001
01011

0000000000
0000000000
0000000000
0000000000
0000000000

1

11010
01100
00101
10001
01011

Critical Output

5

5

0

1

6

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
#define  NODES     26
using namespace std;
int  dfs_matriz[NODES][NODES];
char matriz[NODES][NODES];
int  row, col, area;

void dfs(int x, int y)
{   //cout<<"A>>"<<area<<endl;
    dfs_matriz[x][y] = DFS_BLACK;
    int a=x, b=y;
            if(a-1 >= 0)
            {
                if(dfs_matriz[a-1][b] == DFS_WHITE)
                {
                    area++;
                    dfs(a-1, b);
                }
                if(b+1 < col && dfs_matriz[a-1][b+1] == DFS_WHITE)
                {
                    area++;
                    dfs(a-1, b+1);
                }
                if(b-1 >= 0 && dfs_matriz[a-1][b-1] == DFS_WHITE)
                {
                    area++;
                    dfs(a-1, b-1);
                }
            }
            if(a+1 < row)
            {
                if(b+1 < col && dfs_matriz[a+1][b+1] == DFS_WHITE)
                {
                    area++;
                    dfs(a+1, b+1);
                }
                if(b-1 >= 0 && dfs_matriz[a+1][b-1] == DFS_WHITE)
                {
                    area++;
                    dfs(a+1, b-1);
                }
                if(dfs_matriz[a+1][b] == DFS_WHITE)
                {
                    area++;
                    dfs(a+1, b);
                }
            }
            if(b-1 >= 0 && dfs_matriz[a][b-1] == DFS_WHITE)
            {
                area++;
                dfs(a,b-1);
            }
            if(b+1 < col && dfs_matriz[a][b+1] == DFS_WHITE)
            {
                dfs(a,b+1);
                area++;
            }
}

void readGraph()
{
    string str, data = "";
    row = 0;
    while(getline(cin,str))
    {
        if(str.size() == 0)
           break;
        else
        {
            data += str;
            col = str.size();
            row++;
        }
    }
    int index = 0;
    for(int x=0; x<row; x++)
        for(int y=0; y<col; y++, index++)
        {
            matriz[x][y] = data[index];
            if(matriz[x][y] == '1')
              dfs_matriz[x][y] = DFS_WHITE;
            else
                dfs_matriz[x][y] = 0;
        }
}

void initGraph()
{
    for(int x=0; x<row; x++)
        for(int y=0; y<col; y++)
            if(matriz[x][y] == '1')
               dfs_matriz[x][y] = DFS_WHITE;
}

void print()
{
    for(int x=0; x<row; x++)
    {    for(int y=0; y<col; y++)
        {
            cout<<matriz[x][y];

        }
        cout<<endl;
    }
    cout<<endl<<"DFS\n";
    for(int x=0; x<row; x++)
    {    for(int y=0; y<col; y++)
        {
            cout<<dfs_matriz[x][y];

        }
        cout<<endl;
    }
    cout<<endl;
}

int main()
{
string str;
int casos, maxi;
scanf("%d", &casos);
getline(cin,str);//trash
getline(cin,str);//trashwhile(casos--)
{
    readGraph();
    //print();
    maxi = area = 0;
    for(int x=0; x<row; x++)
        for(int y=0; y<col; y++)
            if(dfs_matriz[x][y] == DFS_WHITE)
            {
               dfs(x,y);
               area++;
               maxi = max(maxi, area);
               area = 0;
            }
    initGraph();
    if(maxi == 0)
       printf("0\n");
    else
        printf("%d\n", maxi);
    if(casos)
       printf("\n");
}
return 0;
}

469 – Wetlands of Florida UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=410

A really easy problem using DFS. Flood fill.

How I did it

• Read the number of cases
• Read the element rows of the matrix.
• If I found a digit, I set the dfs_matriz setting any water grid = -1.
• Read row and column  and class dfs in that point.
• Print the area. Clean the graph.
• If we have more cases to process, print a blank line.
• Accepted.

Hints

• Print a blank line between cases.
• The last case has not a blank line after having processed. If(cases != 0) print a blank line.
• The reading input is tedious, Im using sstream and getline, for simplify this.

Code

#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <sstream>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
#define  MAX 101
using namespace std;

char matriz[MAX][MAX];
int dfs_matriz[MAX][MAX];
int row, col, area;

void dfs(int x, int y)
{
    dfs_matriz[x][y] = DFS_BLACK;
    int a=x, b=y;
            if(a-1 >= 0)
            {
                if(dfs_matriz[a-1][b] == DFS_WHITE)
                {
                    area++;
                    dfs(a-1, b);
                }
                if(b+1 < col && dfs_matriz[a-1][b+1] == DFS_WHITE)
                {
                    area++;
                    dfs(a-1, b+1);
                }
                if(b-1 >= 0 && dfs_matriz[a-1][b-1] == DFS_WHITE)
                {
                    area++;
                    dfs(a-1, b-1);
                }
            }
            if(a+1 < row)
            {
                if(b+1 < col && dfs_matriz[a+1][b+1] == DFS_WHITE)
                {
                    area++;
                    dfs(a+1, b+1);
                }
                if(b-1 >= 0 && dfs_matriz[a+1][b-1] == DFS_WHITE)
                {
                    area++;
                    dfs(a+1, b-1);
                }
                if(dfs_matriz[a+1][b] == DFS_WHITE)
                {
                    area++;
                    dfs(a+1, b);
                }
            }
            if(b-1 >= 0 && dfs_matriz[a][b-1] == DFS_WHITE)
            {
                area++;
                dfs(a,b-1);
            }
            if(b+1 < col && dfs_matriz[a][b+1] == DFS_WHITE)
            {
                dfs(a,b+1);
                area++;
            }
}

void readGraph()
{
    string tmp = "", str;
    int index = 0;
    while(getline(cin, str))
    {
        if(isdigit(str[0]))
           break;
        else
        {
            tmp += str;
            col = str.size();
            row++;
        }
    }

    for(int a=0; a<row; a++)
    {
        for(int b=0; b<col; b++, index++)
        {
            matriz[a][b] = tmp[index];
            if(matriz[a][b] == 'W')
               dfs_matriz[a][b] = DFS_WHITE;
            else
                dfs_matriz[a][b] = 0;
        }
    }

    stringstream ss;
    int flag = 0, x, y, data;
    ss<<str;
    while(ss>>data)
    {
        if(flag == 0)
           x = data;
        else
            y = data;
        flag++;
    }
    dfs(x-1,y-1);
}

void initGraph()
{
    for(int a=0; a<row; a++)
        for(int b=0; b<col; b++)
            if(matriz[a][b] == 'W')
               dfs_matriz[a][b] = DFS_WHITE;
}

int main()
{
string str;
int casos;
scanf("%d", &casos);
getline(cin,str);//trash
getline(cin,str);//trash

while(casos--)
{
    row = col = area = 0;
    readGraph();
    printf("%d\n", area + 1);
    //print();
    stringstream ss;
    int flag, x, y, data;
    while(getline(cin,str))
    {
        if(str.size() == 0)
          break;        flag = 0;
        ss<<str;
        initGraph();
        while(ss>>data)
        {
            if(flag == 0)
               x = data;
            else
                y = data;
            flag++;
        }
        area = 0;
        dfs(x-1,y-1);
        printf("%d\n", area + 1);
        ss.clear();
    }
    if(casos)
       printf("*\n");
}
return 0;
}

10336 – Rank the Languages UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1277

A really easy problem using DFS. Flood fill.

How I did it

• Read the number of cases
• Read the total rows and columns of the matrix.
• Read the graph in a matrix and in other matrix set all the noces with  -1.(dfs_matriz)
• Traverse the matrix.
• Pick the current element and call dfs in the current row and column. Find all adjacent nodes with the same current letter. If there is no more nodes with the same current letter I insert into a map the letter and increment an area.
• After all the traversal in the matrix. I traverse the map and put all the data into a vector.
• Sort the vector with the problem specifications.
• Print the vector.

Hints

• There is not need to check diagonal adjacent nodes.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>
#include <map>
#define  NODES     51
#define  DFS_WHITE -1
#define  DFS_BLACK 1
using namespace std;
int row, column, tmpSize;
char currentLetter;
int dfs_matriz[NODES][NODES];
char matriz[NODES][NODES];

void readGraph()
{
    string str = "", tmp;
    int index = 0;
    for(int a=0; a<row; a++)
    {
        cin>>tmp;
        str += tmp;
    }
    for(int x=0; x<row; x++)
       for(int y=0; y<column; y++, index++)
       {
            matriz[x][y] = str[index];
            dfs_matriz[x][y] = DFS_WHITE;
       }
}

void dfs(int x, int y)
{
    dfs_matriz[x][y] = DFS_BLACK;
    currentLetter =  matriz[x][y];
    int a=x, b=y;
            if(a-1 >= 0)
            {
                if(dfs_matriz[a-1][b] == DFS_WHITE && matriz[a-1][b] == currentLetter)
                    dfs(a-1, b);
            }
            if(a+1 < row)
            {
                if(dfs_matriz[a+1][b] == DFS_WHITE && matriz[a+1][b] == currentLetter)
                    dfs(a+1, b);
            }
            if(b-1 >= 0 && dfs_matriz[a][b-1] == DFS_WHITE && matriz[a][b-1] == currentLetter)
                dfs(a,b-1);
            if(b+1 < column && dfs_matriz[a][b+1] == DFS_WHITE && matriz[a][b+1] == currentLetter)
                dfs(a,b+1);
}

bool cmp(pair<char,int> a, pair<char,int> b)
{
    if(a.second > b.second)
       return true;
    else if(a.second < b.second)
            return false;

    return a.first < b.first;
}

int main()
{
int casos;
scanf("%d", &casos);
for(int w=1; w<=casos; w++)
{
    scanf("%d %d", &row, &column);
    map<char,int> myMap;
    readGraph();
    tmpSize = 0;
    for(int x=0; x<row; x++)
       for(int y=0; y<column; y++)
       {
            if(dfs_matriz[x][y] == DFS_WHITE)
            {
                dfs(x,y);
                myMap[matriz[x][y]]++;
            }
       }
    vector< pair<char,int> > vec;
    for(map<char,int>::iterator it = myMap.begin(); it!=myMap.end(); it++)
    {
        pair<char,int> p = make_pair(it->first,it->second);
        vec.push_back(p);
    }

    sort(vec.begin(), vec.end(), cmp);
    printf("World #%d\n", w);
    for(int m=0; m<vec.size(); m++)
        printf("%c: %d\n", vec[m].first, vec[m].second);

}
return 0;
}

10946 – You want what filled? UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1887

A really easy problem using DFS. Flood Fill.

How I did it

• Read the total rows and columns of the matrix.
• Read the graph in a matrix and in other matrix set any letter with -1.(dfs_matriz)
• Traverse the matrix.
• If the current element in the matrix is equal to any letter,  and is not visited, I call dfs  checking if the adjacent elements are the same letter as the current, with the current row and column. Increment the number of elements.
• If there is no more elements equal to the current element, insert into a vector the letter and total ocurrence.
• Sort the vector, first the most ocurrence, second lexicographic order.
• Print the array.

Hints

• Keep in mind the concept of hole.
• When I call DFS, I check the 8 posibles adjacency vertices. x= row, y=column.
  (x-1, y), (x-1, y+1), (x, y+1), (x+1, y+1), (x+1, y), (x+1, y-1), (x, y-1), (x-1, y-1).

Critical input

2 2
DC
BA
2 2
.A
A.


Critical Output

Problem 1:

A 1

B1

C1

D1

Problem 2:

A 1

A 1

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>
#define  NODES     51
#define  DFS_WHITE -1
#define  DFS_BLACK 1
using namespace std;
int row, column, tmpSize;
char currentLetter;
int dfs_matriz[NODES][NODES];
char matriz[NODES][NODES];

void readGraph()
{
    string str = "", tmp;
    int index = 0;
    for(int a=0; a<row; a++)
    {
        cin>>tmp;
        str += tmp;
    }
    for(int x=0; x<row; x++)
       for(int y=0; y<column; y++, index++)
       {
            matriz[x][y] = str[index];
            if(isalpha(matriz[x][y]))
               dfs_matriz[x][y] = DFS_WHITE;
            else
                dfs_matriz[x][y] = 0;
       }
}

void dfs(int x, int y)
{
    dfs_matriz[x][y] = DFS_BLACK;
    currentLetter =  matriz[x][y];
    int a=x, b=y;
            if(a-1 >= 0)
            {
                if(dfs_matriz[a-1][b] == DFS_WHITE && matriz[a-1][b] == currentLetter)
                {
                    tmpSize++;
                    dfs(a-1, b);
                }
            }
            if(a+1 < row)
            {
                if(dfs_matriz[a+1][b] == DFS_WHITE && matriz[a+1][b] == currentLetter)
                {
                    tmpSize++;
                    dfs(a+1, b);
                }
            }
            if(b-1 >= 0 && dfs_matriz[a][b-1] == DFS_WHITE && matriz[a][b-1] == currentLetter)
            {
                tmpSize++;
                dfs(a,b-1);
            }
            if(b+1 < column && dfs_matriz[a][b+1] == DFS_WHITE && matriz[a][b+1] == currentLetter)
            {
                tmpSize++;
                dfs(a,b+1);
            }
}

bool cmp(pair<char, int> a, pair<char, int> b)
{
    if(a.second > b.second)
       return true;
    else if(a.second < b.second)
            return false;
    return a.first<b.first;
}

int main()
{
int casos = 1;
while(scanf("%d %d", &row, &column))
{
if(!row && !column)
   break;

    readGraph();
    tmpSize = 0;
    vector< pair<char, int> > vec;
    for(int x=0; x<row; x++)
       for(int y=0; y<column; y++)
       {
            if(dfs_matriz[x][y] == DFS_WHITE)
            {
                dfs(x,y);
                pair<char,int> p = make_pair(currentLetter, tmpSize + 1);
                vec.push_back(p);
                //cout<<"El tam del grupo es: "<<currentLetter<<"  "<<tmpSize<<endl;
                tmpSize = 0;
            }
       }
    sort(vec.begin(), vec.end(), cmp);
    printf("Problem %d:\n",casos++);

    for(int x=0; x<vec.size(); x++)
        printf("%c %d\n",vec[x].first, vec[x].second);
}
return 0;
}

11244 – Counting Stars UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2201

A really easy problem using DFS. Connected components.

How I did it

• Read the total rows and columns of the matrix.
• Read the graph in a matrix and in other matrix set * with -1.(dfs_sky)
• Traverse the matrix.
• If the current element in the matrix is equal to “*” or  (dfs_sky == -1) and is not visited, I call dfs with the current row and column. Increment the number of elements.
• If the counted number of elements in the loop is equal to 1. I add one star counter.

Hints

• The matrix is small 101 * 101.
• When I call DFS, I check the 8 posibles adjacency vertices. x= row, y=column.
  (x-1, y), (x-1, y+1), (x, y+1), (x+1, y+1), (x+1, y), (x+1, y-1), (x, y-1), (x-1, y-1).

Code

#include <iostream>
#include <cstdio>
#include <vector>
#define  NODES      101
#define  DFS_WHITE  -1
#define  DFS_BLACK  1
using namespace std;
int dfs_sky[NODES][NODES];
char sky[NODES][NODES];
int row, column, group;

void readGraph()
{
    string str = "", tmp;
    int index = 0;
    for(int x=0; x<row; x++)
    {
        cin>>tmp;
        str+=tmp;
    }
    for(int a=0; a<row; a++)
    {
        for(int b=0; b<column; b++, index++)
        {
            sky[a][b] = str[index];
            if(sky[a][b] == '.')
              dfs_sky[a][b] = 0;
            else
                dfs_sky[a][b] = DFS_WHITE;
        }
    }
}

void dfs(int x, int y)
{
    dfs_sky[x][y] = DFS_BLACK;
    group++;
    int a=x, b=y;
            if(a-1 >= 0)
            {
                if(dfs_sky[a-1][b] == DFS_WHITE)
                   dfs(a-1, b);
                if(b+1 < column && dfs_sky[a-1][b+1] == DFS_WHITE)
                   dfs(a-1, b+1);
                if(b-1 >= 0 && dfs_sky[a-1][b-1] == DFS_WHITE)
                   dfs(a-1, b-1);
            }
            if(a+1 < row)
            {
                if(b+1 < column && dfs_sky[a+1][b+1] == DFS_WHITE)
                   dfs(a+1, b+1);
                if(b-1 >= 0 && dfs_sky[a+1][b-1] == DFS_WHITE)
                   dfs(a+1, b-1);
                if(dfs_sky[a+1][b] == DFS_WHITE)
                   dfs(a+1, b);
            }
            if(b-1 >= 0 && dfs_sky[a][b-1] == DFS_WHITE)
               dfs(a,b-1);
            if(b+1 < column && dfs_sky[a][b+1] == DFS_WHITE)
               dfs(a,b+1);
}

int main()
{
while(scanf("%d %d", &row, &column))
{
    if(!row && !column)
       break;
    readGraph();
    group = 0;
    int cc = 0;
    for(int x=0; x<row; x++)
    {
        for(int y=0; y<column; y++)
        {
           if(dfs_sky[x][y] == DFS_WHITE)
           {
               dfs(x,y);
               if(group == 1)
                  cc++;
                group = 0;
           }
        }
    }
    printf("%d\n", cc);
}
return 0;
}

10305 – Ordering Tasks UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1246

A really easy problem using DFS. ropological sort, DAG.

How I did it

• Read the number of vertices and edges.
• Read the graph as a Adjacency List data structure.
• Traverse the graph.
• If the current element in the graph is not visited yet, I call dfs.
• Reverse the answer vector.
• Print the answer vector.
• Accepted!

Hints

• The graph is DAG(Direct acyclic graph).
• Topological sort solve this problem.
• My snippet only has a little variant of connected components.(DFS)

Code

#include <iostream>
#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
using namespace std;
typedef vector<int> vi;

vector<vi> graph;
vi dfs_num, answer;

void readGraph(int edges)
{
    int vertex1, vertex2;
    for(int i=1; i<=edges; i++)
    {
        scanf("%d %d", &vertex1, &vertex2);
        graph[vertex1 - 1].push_back(vertex2 - 1);
    }
}

void dfs(int node)
{
    dfs_num[node] = DFS_BLACK;
    for(int x=0; x<graph[node].size(); x++)
       if(dfs_num[graph[node][x]] == DFS_WHITE)
          dfs(graph[node][x]);
    answer.push_back(node);
}

int main()
{
int vertices, edges;
while(scanf("%d %d", &vertices, &edges))
{
    if(!vertices && !edges)
       break;
    graph.assign(vertices, vi());
    dfs_num.assign(vertices, DFS_WHITE);
    readGraph(edges);

    for(int x=0; x<graph.size(); x++)
       if(dfs_num[x] == DFS_WHITE)
          dfs(x);

    reverse(answer.begin(), answer.end());
    for(int x=0; x<answer.size(); x++)
    {
        if(x<answer.size() - 1)
           printf("%d ", answer[x]+1);
        else
            printf("%d\n", answer[x]+1);
    }
    answer.clear();
}
return 0;
}