UVa : 336 :: A Node Too Far

Problem : Please find the problem here.

Explanation : The problem basically asked and suggest to traverse the graph with BFS from a given node upto a given level. Remember that, BFS visit vertices that are direct neighbors of the source vertex (first layer), neighbors of direct neighbors (second layer), and so on, layer by layer. To identify which layer the given vertex belongs to, we can push the vertex with its level from the starting node in the queue. One more thing, the number of vertices are not given, so I made a edge-list first, mapped all the elements to the integers starting from zero, later created an adjacency-list with the given edge-list.

Code : Used BFS.

#include <bits/stdc++.h>
//#define debug
using namespace std;

const int mxN = 1e3;
int n, m;
vector<int> adj[mxN];
map<int, int> node_id;
vector<array<int, 2>> edges;
bool vis[mxN];

int bfs(int node, int time){

    memset(vis, false, sizeof(vis));

    queue<array<int, 2>> qu;
    qu.push({node, time});
    vis[node] = 1;
    while(qu.size()){
	array<int, 2> u = qu.front();
	qu.pop();
	if(u[1]){
	    for(int v : adj[u[0]]){
		if(!vis[v]){
		    qu.push({v, u[1]-1});
		    vis[v] = 1;
		}
	    }
	}

    }
    // now counting the NOT_VISITED nodes;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(!vis[i]){
	    cnt++;
	}
    }
    return cnt;
}

void init(){

    edges.clear();

    node_id.clear();

    memset(vis, false, sizeof(vis));
    for(int i = 0; i < n; i++){
	adj[i].clear();
    }
}

void set_adj(){
    for(auto it : edges){
	adj[it[0]].emplace_back(it[1]);
	adj[it[1]].emplace_back(it[0]);
    }
}

int main()
{
    int __case = 1;
    while(cin >> m){
	int id = 0;
	init();
	for(int i = 0, u, v; i < m; i++){
	    cin >> u >> v;
	    if(node_id.find(u) == node_id.end()){
#ifdef debug
	        cout << u << " is mapped to " << id << '\n';
#endif
	        node_id[u] = id++;
	    }
	    if(node_id.find(v) == node_id.end()){
#ifdef debug

                cout << v << " v is mapped to " << id << '\n';
#endif
		node_id[v] = id++;
	    }
	    u = node_id[u], v = node_id[v];
	    edges.push_back({u, v});
	}
	n = node_id.size();
	set_adj();
#ifdef debug
	cout << "printing adjacency list\n";
	for(int i = 0; i < n; i++){
	    cout << i << "->";
	    for(int u : adj[i]){
		cout << u << ' ';
	    }
	    cout << '\n';
	}
#endif
	int node, time;
	while(cin >> node >> time && (node || time)){
	    printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",__case++, bfs(node_id[node], time), node, time);
	}
    }	
    return 0;
}

UVa : 260 :: II Gioco dell'X

Problem : Please find the problem here.

Explanation : Check, for black, if there's path from first row to last row OR for white, if there's path from first column to last column. Notice that as stated in the problem statement that both black and white can never win, its either black or white, that means you dont need to check for both white and black, as if one wins, other loses ans vice-versa. 

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 200, di[6]={-1, -1, 0, 0, 1, 1}, dj[6]={-1, 0, -1, 1, 0, 1};
int n;
string s[mxN];
bool vis[mxN][mxN];

bool isok(int i, int j){
	return i>=0 && i<n && j>=0 && j< n && !vis[i][j];
}

void dfs(int i, int j){
	vis[i][j] = 1; 
	for(int k = 0; k < 6; k++){
		int ni = i+di[k], nj = j+dj[k];
		if(isok(ni, nj) && s[ni][nj] == s[i][j]){
			dfs(ni, nj);
		}
	}
}

int main()
{	
	ofstream fout("out");
	int t = 1;
	while(cin >> n  && n){
		for(int i = 0; i < n; i++){
			cin >> s[i];
		}
		bool ok = 0;
		memset(vis, false, sizeof(vis));
		for(int i = 0; i < n; i++){
			if(s[i][0] == 'w'){
				dfs(i, 0);
			}
		}
		for(int i = 0; i < n; i++){
			if(vis[i][n-1]){
				ok = 1;
				break;
			}
		}
		cout << t++ << ' ' << (ok?'W':'B') << '\n';
	}	
	return 0;
}

UVa : 784 :: Maze Exploration

Problem : Please find the problem here.

Explanation : Simple DFS. 

Code :

#include <bits/stdc++.h>
using namespace std;

const int mxN = 30, di[4]={1, 0, -1, 0}, dj[4]={0, 1, 0, -1};
int n, m, si, sj;
string s[mxN], in, br;

bool isok(int i, int j){
    return i>=0 && i<n && j>=0 && j<(int)s[i].length() && s[i][j] == ' ';
}

void dfs(int i, int j){
    s[i][j] = '#'; 
    for(int k = 0; k < 4; k++){
	int ni = i+di[k], nj = j+dj[k];
	if(isok(ni, nj)){
	    dfs(ni, nj);
	}
    }
}

int main()
{	
    ofstream fout("out");
    int t;
    cin >> t;
    getline(cin, in); // read the newline character at the start
    for(int k = 0; k < t; k++){
	in.clear();
	getline(cin, in);  // read maze from here
	int i = 0;
	while(1){
	    if(in[0] == '_'){ // break if hit the partition line
		br = in;
		break;
	    }
	    s[i] = in;
	    for(int j = 0; j < (int)s[i].length(); j++){
		if(s[i][j] == '*'){
		    si = i, sj = j; s[i][j] = '#';
		}
	    }
	    i++;
	    getline(cin, in);
	}
	n = i
	dfs(si, sj);
	for(int j = 0; j < n; j++){
	    cout << s[j] << '\n';
	}
	cout << br << '\n';
    }
    return 0;
}

UVa : 10946 :: You want what filled?

Problem : Please find the problem here.

Explanation : We are basically asked to find the connected components in the graph and print them in non increasing order along with the charcter in each connected component printed in increasing order. 

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define debug

const int mxN = 60, di[4]={1, 0, -1, 0}, dj[4]={0, 1, 0, -1};
int n, m, cnt;
string s[mxN];
vector<pair<char, int>> ans;
bool vis[mxN][mxN];

bool isok(int i, int j){
    return i>=0 && i<n && j>=0 && j<m && s[i][j] != '.' && !vis[i][j];
}

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

void dfs(int i, int j){
    vis[i][j] = 1;
    for(int k = 0; k < 4; k++){
        int ni = i+di[k], nj = j+dj[k];
        if(isok(ni, nj) && s[i][j] == s[ni][nj]){
	    dfs(ni, nj);
	}
    }
    cnt++;
}

int main()
{
    ofstream fout("out");
    int t = 1;
    while(cin >> n >> m && (n||m)){
        for(int i = 0; i < n; i++){
	    cin >> s[i];
        }
	memset(vis, false, sizeof(vis));
	ans.clear();
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < m; j++){
		if(isok(i, j)){
		    cnt = 0;
		    dfs(i, j);
		    ans.push_back(mp(s[i][j], cnt));
	        }
	    }
	}
	sort(ans.begin(), ans.end(), cmp);
	cout << "Problem " << t++ << ":\n";
	for(auto a : ans){
	    cout << a.first << ' ' << a.second << '\n';
	}
    }
    return 0;
}

UVa : 785 :: Grid Colouring

Problem : Please find the problem here.

Explanation : Just need to traverse the graph, could be solved by DFS or BFS. Input parsing is troublesome though. Good for practice.  

Code : Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 32, di[4]={1, 0, -1, 0}, dj[4]={0, 1, 0, -1};
int n, m;
string s[mxN], in, br;
char contour;

bool isok(int i, int j){
    return i>=0 && i<n && j>=0 && j<(int)s[i].length() && s[i][j] == ' ';
}

void dfs(int i, int j, char c){
    s[i][j] = c;
    for(int k = 0; k < 4; k++){
        int ni = i+di[k], nj = j+dj[k];
	if(s[ni][nj] != c && isok(ni, nj)){ 
	    dfs(ni, nj, c);
	}
    }
}

int main()
{
    ofstream fout("out");
    while(getline(cin, in)){
	int i = 0;
	do{
	    if(in[0] == '_'){
	        br = in;
	        break;
	    }
	    s[i] = in;

	    // lazy way to find contour,
	    if(i == 0){
		for(int j = 1; j < (int)in.length(); j++){
		    if(in[j]!=' ' && in[j]!='_' && in[j]==in[j-1]){
			contour = in[j];
			break;
		    }
		}
	    }
	    // ends here
	    i++;
	}while(getline(cin, in));
	

        n = i;

        // now look for marker and apply dfs from that point.
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < (int)s[i].length(); j++){
		if(s[i][j] != contour && s[i][j] != ' ' && s[i][j] != '\t'){
		    dfs(i, j, s[i][j]);
		}
	    }
	}

	// finally print the grid.
	for(int i = 0; i < n; i++){
	    cout << s[i] << '\n';
	}

	// dont forget the seperation line -> "_______"
	cout << br << '\n';
    }	
    return 0;
}