A solution for the Minesweeper problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/101/10189.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.03.08

/* 
 * A solution for the Minesweeper problem.
 * UVa ID: 10189
 */
#include <stdio.h>

#define MINE '*'
#define MATRIX_OFFSET 1

int main (int argc, const char * argv[]) {
	/* number of lines of the mine field */
	long n;
	
	/* number of colums of the mine field */
	long m;
	
	/* iterators for retrieving the content of each field line*/
	long i, j;
	
	/* field number identifier */
	long fieldNumber = 0;

	while(scanf("%ld %ld", &n, &m) != EOF) {
			
		/* 0 0, ends the program */
		if (!n && !m) {
			return 0;
		} else {
			if (fieldNumber > 0) {
				/* 
				 * workaround for the extra line on the output, 
				 * which was giving me a Wrong Answer verdict..
				 * so only insert an extra line if there's more
				 * to come :-) 
				 */
				printf("\n");
			}
		}
		
		/* increment field id */
		fieldNumber++;
				
		/* a bidimensional array representing the input mine field */
		char inputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* a bidimensional array to output the mine field */
		int outputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* temporary variable to retrieve mine field lines */
		char line[m];
		
		/* init, O(n2) */
		for (i = 0; i < n + MATRIX_OFFSET + 1; i++) {
			for (j = 0; j < m + MATRIX_OFFSET + 1; j++) {
				outputField[i][j] = 0;
			}
		}
		
		/* read mine field, O(n2) */
		for (i = 0; i < n; i++) {
			scanf("%s\n",line);
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				inputField[i + MATRIX_OFFSET][j] = line[j - MATRIX_OFFSET];
			}
		}
		
		/* update output, O(n2) */ 
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE) {
				
					/* upper neighbours */
					outputField[i-1][j-1]++;
					outputField[i-1][j]++;
					outputField[i-1][j+1]++;
					
					/* same level neighbours */
					outputField[i][j-1]++;
					outputField[i][j+1]++;
					
					/* lower neighbours */
					outputField[i+1][j-1]++;
					outputField[i+1][j]++;
					outputField[i+1][j+1]++;
				}
			}
		}
		
		/* present output, O(n2) */
		printf("Field #%ld:\n",fieldNumber);
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE)
					printf("%c", MINE);
				else	
					printf("%d",outputField[i][j]);
			}
			printf("\n");
		}

	}

    return 0;
}

A simple way to check command line arguments.

Author: Joana Matos Fonseca da Trindade
Date: 2008.02.25

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* minimum required number of parameters */
#define MIN_REQUIRED 2

/* display usage */
int help() {
   printf("Usage: myprogram [-s <arg0>] [-n <arg1>] [-true]\n");
   printf("\t-s: a string a\n");
   printf("\t-n: a number\n");
   printf("\t-true: a single parameter\n");

   return 1;
}

/* main */
int main(int argc, char *argv[]) {
   if (argc < MIN_REQUIRED) {
      return help();
   }
   int i;

   /* iterate over all arguments */
   for (i = 1; i < (argc - 1); i++) {
       if (strcmp("-s", argv[i]) == 0) {
          /* do something with it */ 
          printf("string = %s\n", argv[++i]);
          continue;
       }
       if (strcmp("-n", argv[i]) == 0) {
          /* do something with it. for example, convert it to an integer */
          printf("number = %i\n", atoi(argv[++i]));
          continue;
       }
       if (strcmp("-true", argv[i]) == 0) {
          printf("true activated\n");
          continue;
       }
       return help();
   }
   return 0;
}

Function to generate descriptive errors (line number, function name, etc).

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>

#ifdef __OPTIMIZE__
#define __OPT__ 1
#else
#define __OPT__ 0
#endif

#ifdef __OPTIMIZE_SIZE__
#define __OPT_SIZE__ 1
#else
#define __OPT_SIZE__ 0
#endif

#define err_print(args...) __err_print(__FILE__, __FUNCTION__, __LINE__, __DATE__ " " __TIME__, __VERSION__, __OPT__, __OPT_SIZE__, ##args)
void __err_print(char *file, char *function, int line, char *date, char *version, int opt, int opt_size, char *txt, ...)
{
        va_list argp;

        puts("** ERROR! **");
        printf("File:                 \t %s\n",file);
        printf("Function:             \t %s\n",function);
        printf("Line:                 \t %d\n",line);
        printf("Compilation date:     \t %s\n",date);
        printf("Compilator version:   \t %s\n",version);
        printf("Optimization:         \t %s\n",opt==1 ? "Yes" : "No");
        printf("Size optimization:    \t %s\n",opt_size==1 ? "Yes" : "No");

        if (txt == NULL)
                return;
        puts("Description:\n>>>");
        va_start(argp, txt);
        vprintf(txt, argp);
        va_end(argp);
        puts("\n<<<");
}

void other_function() {
        err_print("other %s (%d+%d=%d)", "description",2,2,5);
}

int main() {
        err_print("test %d", 2);
        puts("");
        other_function();
        return 0;
}

Demonstrates a way of speeding up the O(n²) version of Dijkstra's Algorithm by about 4x.

Here, dist[][] is the adjacency matrix representing the graph and n is the number of nodes. d2[] is where the lengths of the shortest paths are saved.

For a full explanation, see this.

void dijkstra2(int s) {
	int queue[GRAPHSIZE];
	char inQueue[GRAPHSIZE];
	int begq = 0,
	    endq = 0;
	int i, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d2[i] = INFINITY;
		visited[i] = 0; /* the i-th element has not yet been visited */
		inQueue[i] = 0;
	}

	d2[s] = 0;
	queue[endq] = s;
	endq = (endq + 1) % GRAPHSIZE;


	while (begq != endq) {
		mini = queue[begq];
		begq = (begq + 1) % GRAPHSIZE;
		inQueue[mini] = 0;

		visited[mini] = 1;

		for (i = 1; i <= n; ++i)
			if (dist[mini][i])
				if (d2[mini] + dist[mini][i] < d2[i]) { 
					d2[i] = d2[mini] + dist[mini][i];
					if (!inQueue[i]) {
						queue[endq] = i;
						endq = (endq + 1) % GRAPHSIZE;
						inQueue[i] = 1;
					}
				}
	}
}

This is a simple implementation of the Gaussian Elimination algorithm for solving n linear equations with n unknowns.

Further explanation is given here.

#include <stdio.h>

int n;
float a[10][11];

void forwardSubstitution() {
	int i, j, k, max;
	float t;
	for (i = 0; i < n; ++i) {
		max = i;
		for (j = i + 1; j < n; ++j)
			if (a[j][i] > a[max][i])
				max = j;
		
		for (j = 0; j < n + 1; ++j) {
			t = a[max][j];
			a[max][j] = a[i][j];
			a[i][j] = t;
		}
		
		for (j = n; j >= i; --j)
			for (k = i + 1; k < n; ++k)
				a[k][j] -= a[k][i]/a[i][i] * a[i][j];

/*		for (k = 0; k < n; ++k) {
			for (j = 0; j < n + 1; ++j)
				printf("%.2f\t", a[k][j]);
			printf("\n");
		}*/
	}
}

void reverseElimination() {
	int i, j;
	for (i = n - 1; i >= 0; --i) {
		a[i][n] = a[i][n] / a[i][i];
		a[i][i] = 1;
		for (j = i - 1; j >= 0; --j) {
			a[j][n] -= a[j][i] * a[i][n];
			a[j][i] = 0;
		}
	}
}

void gauss() {
	int i, j;

	forwardSubstitution();
	reverseElimination();
	
	for (i = 0; i < n; ++i) {
		for (j = 0; j < n + 1; ++j)
			printf("%.2f\t", a[i][j]);
		printf("\n");
	}
}

int main(int argc, char *argv[]) {
	int i, j;

	FILE *fin = fopen("gauss.in", "r");
	fscanf(fin, "%d", &n);
	for (i = 0; i < n; ++i)
		for (j = 0; j < n + 1; ++j)
			fscanf(fin, "%f", &a[i][j]);
	fclose(fin);
	
	gauss();
	
	return 0;
}

// description of your code here

#include <stdio.h>
int main()
{
printf("test");
}

This is a simple O(n^2) implementation of Dijkstra's algorithm for finding the shortest paths from a single source to all nodes in a graph.

Further explanation is given here.

#include <stdio.h>

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */

void printD() {
	int i;
	for (i = 1; i <= n; ++i)
		printf("%10d", i);
	printf("\n");
	for (i = 1; i <= n; ++i) {
		printf("%10ld", d[i]);
	}
	printf("\n");
}

void dijkstra(int s) {
	int i, k, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d[i] = INFINITY;
		visited[i] = 0; /* the i-th element has not yet been visited */
	}

	d[s] = 0;

	for (k = 1; k <= n; ++k) {
		mini = -1;
		for (i = 1; i <= n; ++i)
			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
				mini = i;

		visited[mini] = 1;

		for (i = 1; i <= n; ++i)
			if (dist[mini][i])
				if (d[mini] + dist[mini][i] < d[i]) 
					d[i] = d[mini] + dist[mini][i];
	}
}

int main(int argc, char *argv[]) {
	int i, j;
	int u, v, w;

	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &e);
	for (i = 0; i < e; ++i)
		for (j = 0; j < e; ++j)
			dist[i][j] = 0;
	n = -1;
	for (i = 0; i < e; ++i) {
		fscanf(fin, "%d%d%d", &u, &v, &w);
		dist[u][v] = w;
		n = MAX(u, MAX(v, n));
	}
	fclose(fin);

	dijkstra(1);

	printD();

	return 0;
}

This is a simple implementation of the Bellman-Ford algorithm for finding the shortest path from a single source in a graph.

A detailed explanation is given here.

#include <stdio.h>

typedef struct {
	int u, v, w;
} Edge;

int n; /* the number of nodes */
int e; /* the number of edges */
Edge edges[1024]; /* large enough for n <= 2^5=32 */
int d[32]; /* d[i] is the minimum distance from node s to node i */

#define INFINITY 10000

void printDist() {
	int i;

	printf("Distances:\n");

	for (i = 0; i < n; ++i)
		printf("to %d\t", i + 1);
	printf("\n");

	for (i = 0; i < n; ++i)
		printf("%d\t", d[i]);

	printf("\n\n");
}

void bellman_ford(int s) {
	int i, j;

	for (i = 0; i < n; ++i)
		d[i] = INFINITY;

	d[s] = 0;

	for (i = 0; i < n - 1; ++i)
		for (j = 0; j < e; ++j)
			if (d[edges[j].u] + edges[j].w < d[edges[j].v])
				d[edges[j].v] = d[edges[j].u] + edges[j].w;
}

int main(int argc, char *argv[]) {
	int i, j;
	int w;

	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &n);
	e = 0;

	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j) {
			fscanf(fin, "%d", &w);
			if (w != 0) {
				edges[e].u = i;
				edges[e].v = j;
				edges[e].w = w;
				++e;
			}
		}
	fclose(fin);

	/* printDist(); */

	bellman_ford(0);

	printDist();

	return 0;
}

If you have two implementations and are unsure which one's the keeper - this may just be what you need.
Imagine you are just working on some performance critical function/method and have to run some tests. Commenting out and changing stuff can be quite tedious if it involves lot's of code changes. With this snippet, you only have to delete (or add) one character to toggle between your options.
Here's how it's done.

...
//*
option1();
/*/
option2();
//*/
...
// option1() is used...

Delete the first

/

and the second option is used.

...
/*
option1();
/*/
option2();
//*/
...
// option2() is used...

If you re-add it, option 1 becomes active again.
So how is this done?
If you start with "//*" the line is a line comment ("*" is commented out).
"/*" starts a block comment instead. "/*/" is either an opening block comment or a closing block comment.
"//*/" is the end of a block comment when inside one - or it's a line comment commenting out "*/".

This is a dynamic-programming algorithm implementation for solving the the 0-1 Knapsack Problem in C.

Further explanation is given here.

#include <stdio.h>

#define MAXWEIGHT 100

int n = 3; /* The number of objects */
int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
				YOU PAY to take the object */
int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
				what YOU GET for taking the object */
int W = 10; /* The maximum weight you can take */ 

void fill_sack() {
	int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
				using at most i weight */
	int last_added[MAXWEIGHT]; /* I use this to calculate which object were
					added */
	int i, j;
	int aux;

	for (i = 0; i <= W; ++i) {
		a[i] = 0;
		last_added[i] = -1;
	}

	a[0] = 0;
	for (i = 1; i <= W; ++i)
		for (j = 0; j < n; ++j)
			if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
				a[i] = a[i - c[j]] + v[j];
				last_added[i] = j;
			}

	for (i = 0; i <= W; ++i)
		if (last_added[i] != -1)
			printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);
		else
			printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);

	printf("---\n");

	aux = W;
	while ((aux > 0) && (last_added[aux] != -1)) {
		printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
		aux -= c[last_added[aux]];
	}

	printf("Total value added: %d$\n", a[W]);
}

int main(int argc, char *argv[]) {
	fill_sack();

	return 0;
}