417 - Word Index, uva, solution

simple BFS using a queue.

#include <iostream> 
#include <sstream> 
#include <cstring> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <ctime> 
#include <cctype> 
#include <cmath> 
#include <vector> 
#include <map> 
#include <set> 
#include <queue>
#include<bitset>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
 #endif
 string s;
 map<string, int> mapa;
 queue<string> q;
 q.push("");
 int cont = 0;
 while (!q.empty()) {
  string val = q.front();
  q.pop();
  mapa[val] = cont++;
  if (val.size() == 5) continue;
  for (char i = (val == "") ? 'a' : val[val.size() - 1] + 1; i < 'z' + 1; i++) {
   q.push(val + i);
  }
 }
 char linea[6];
 while (gets(linea)) { 
  printf("%d\n", mapa[linea]); 
 }
 return 0;
}

11520 - Fill the Square, uva, solution

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define listar(lista) for (int i = 0; i < lista.size(); i++) db(lista[i])
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int dirx[] = {0, 0, -1, 1};
int diry[] = {-1, 1, 0, 0};
vector<string> matriz;
int n;
void llenar (int x, int y) {
 if (x < 0 || x >= n || y < 0 || y >= n || matriz[x][y] != '.') return;
 for (char i = 'A'; i < 'Z' + 1; i++) {
  bool can = true;
  for (int k = 0; k < 4; k++) {
   if (x + dirx[k] >= 0 && 
    x + dirx[k] < n &&
    y + diry[k] >= 0 &&
    y + diry[k] < n && matriz[x + dirx[k]][y + diry[k]] == i)
    can = false;
  }
  if (can)  {
   matriz[x][y] = i;
   break;
  }
 } 
}
int main() {
 int t, caso;
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 scanf("%d", &t);
 caso = t;
 while (t--) {
  scanf("%d", &n);
  matriz.resize(n);
  for (int i = 0; i < n; i++) {
   cin >> matriz[i];
  }
  for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
    llenar(i, j);
   }
  }
  
  printf("Case %d:\n", caso - t);
  
  for (int i = 0; i < n; i++) {
   cout << matriz[i] << endl;
  }
  
 }
 return 0;
}

10336 - Rank the Languages, uva, solution

This can be done with both DFS or BSF graph traversal.

#include <iostream> 
#include <sstream> 
#include <cstring> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <ctime> 
#include <cctype> 
#include <cmath> 
#include <vector> 
#include <map> 
#include <set> 
#include <queue>
#include<bitset>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
using namespace std;
vector<string> lista;
int h, w;
void dfs(int i, int j, char cur) {
 if (i >= 0 && i < h && j >= 0 && j < w && lista[i][j] == cur) {
  lista[i][j] = '-';
  dfs(i + 1, j, cur);
  dfs(i - 1, j, cur);
  dfs(i, j - 1, cur);
  dfs(i, j + 1, cur);
 }
}
bool def(int i, int j, char cur) {
 if (i > 0 && lista[i - 1][j] == cur) return true;
 if (i < h - 1 && lista[i + 1][j] == cur) return true;
 if (j > 0 && lista[i][j - 1] == cur) return true;
 if (j < w - 1 && lista[i][j + 1] == cur) return true;
 return false;
}
bool cmp(const pair<char, int>& a, const pair<char, int>& b) {
 if (a.second > b.second) return true;
 return a.first < b.first;
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int t;
 string s;
 set<char> sc;
 cin >> t;
 int start = t;
 while (t--) {
  cin >> h >> w;
  lista.resize(h);
  for (int i = 0; i < h; i++) {
   cin >> lista[i];
  }
  map<char, int> mapa;
  sc.clear();
  for (int i = 0; i < h; i++) {
   for (int j = 0; j < w; j++) {
    if (lista[i][j] != '-' && def(i, j, lista[i][j])) {
     char cur = lista[i][j];
     mapa[cur]++;
     sc.insert(cur);
     dfs(i, j, cur);
    }
   }
  }
  printf("World #%d\n", start - t);
  vector< pair<char,int> > res;
  foreach(it, mapa) {
   res.push_back(make_pair(it->first, it->second));
  }
  sort(res.begin(), res.end(), cmp);
  for (int i = 0; i < res.size(); i++) {
   cout << res[i].first << ": " << res[i].second << endl;
  }
 }
 return 0;
}