[Assorted-commits] SF.net SVN: assorted: [861] problems

[<yan...@us...>]

Revision: 861
          http://assorted.svn.sourceforge.net/assorted/?rev=861&view=rev
Author:   yangzhang
Date:     2008-07-01 23:34:48 -0700 (Tue, 01 Jul 2008)

Log Message:
-----------
added gcj 06 entry

Added Paths:
-----------
    problems/gcj/
    problems/gcj/2006/
    problems/gcj/2006/cjam.cpp

Added: problems/gcj/2006/cjam.cpp
===================================================================
--- problems/gcj/2006/cjam.cpp	                        (rev 0)
+++ problems/gcj/2006/cjam.cpp	2008-07-02 06:34:48 UTC (rev 861)
@@ -0,0 +1,128 @@
+// Hareesh Nagarajan <hareesh AT symonds.net>
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <cstring>
+#include <cassert>
+#define ROW_MAX		50
+#define COL_MAX		50
+#define PATH_STR_MAX 	(1<<10)
+#define INF		100000000
+using namespace std;
+
+typedef struct { int i, j; } point;
+
+static inline void get_neighbors(const char grid[ROW_MAX][COL_MAX], const int i, const int j,
+				 const int rows, const int cols, vector<point> &vp)
+{
+	point p;
+	bool i_minus_1, i_plus_1, j_minus_1, j_plus_1;
+	int sub_i, add_i, sub_j, add_j;
+
+	i_minus_1 = i_plus_1 = j_minus_1 = j_plus_1= false;
+	sub_i = i - 1;
+	add_i = i + 1;
+	sub_j = j - 1;
+	add_j = j + 1;
+	
+	if(sub_i >= 0) i_minus_1 = true;
+	if(add_i < rows) i_plus_1 = true;
+
+	if(sub_j >= 0) {
+		j_minus_1 = true; p.i = i; p.j = sub_j; vp.push_back(p);	//i, j-1
+	}
+	
+	if(add_j < cols) {
+		j_plus_1 = true; p.i = i; p.j = add_j; vp.push_back(p);		//i, j+1
+	}
+	
+	if(i_minus_1) {
+		p.i = sub_i; p.j = j; vp.push_back(p); 				//i-1, j
+		if(j_minus_1) { p.j = sub_j; vp.push_back(p); } 		//i-1, j-1
+		if(j_plus_1) { p.j = add_j; vp.push_back(p); } 			//i-1, j+1
+	}
+	
+	if(i_plus_1) {
+		p.i = add_i; p.j = j; vp.push_back(p); 				//i+1, j
+		if(j_minus_1) { p.j = j - 1; vp.push_back(p); } 		//i+1, j-1
+		if(j_plus_1) { p.j = j + 1; vp.push_back(p); } 			//i+1, j+1
+	}
+}
+
+	
+
+int compute(const char grid[ROW_MAX][COL_MAX], const char path[PATH_STR_MAX],
+	    int &count, int i, int j, int rows, int cols, int path_iter, const int path_sz)
+{
+	if(path_iter >= path_sz) { count++; return 0; }
+        if(count > INF) return -1;
+	vector<point> neighbors;
+	vector<point>::iterator iter;
+	
+	neighbors.reserve(8);
+	get_neighbors(grid, i, j, rows, cols, neighbors);
+
+	for(iter = neighbors.begin(); iter < neighbors.end(); iter++) {
+		if(grid[iter->i][iter->j] == path[path_iter])
+			compute(grid, path, count, iter->i, iter->j, rows, cols, path_iter + 1, path_sz);
+	}
+
+	return 1;
+}
+
+
+int search_paths(const char grid[ROW_MAX][COL_MAX], const char path[PATH_STR_MAX],
+		 int rows, int cols, const int path_sz)
+{
+	int i, j, count;
+	count = 0;
+
+	for(i = 0; i < rows; i++) {
+		for(j = 0; j < cols; j++) {
+			if(grid[i][j] == path[0]) {
+				if(compute(grid, path, count, i, j, rows, cols, 1, path_sz) < 0)
+					return -1;
+			}
+		}
+	}
+	return count;
+}
+
+main()
+{
+	char path[PATH_STR_MAX];
+	int rows, cols, path_sz;
+
+	char grid[ROW_MAX][COL_MAX] = {
+		{'A','A','A','A','A'},
+		{'A','A','A','A','A'},
+		{'A','A','A','A','A'},
+		{'A','A','A','A','A'},
+		{'A','A','A','A','A'}
+	};
+	strcpy(path, "AAAAAAAAAAA");
+
+	rows = 5;
+	cols = 5;
+	path_sz = strlen(path);
+
+//	char grid[ROW_MAX][COL_MAX] = {
+//		{'A','B','A','B','A'},
+//		{'B','A','B','A','B'},
+//		{'A','B','A','B','A'},
+//		{'B','A','B','A','B'},
+//		{'A','B','A','B','A'}
+//	};
+//	strcpy(path, "ABABABBA");
+//
+//	rows = 5;
+//	cols = 5;
+//	path_sz = strlen(path);
+
+	assert(rows < ROW_MAX);
+	assert(cols < COL_MAX);
+	assert(path_sz < PATH_STR_MAX);
+
+	cout << search_paths(grid, path, rows, cols, path_sz) << endl;
+}


Property changes on: problems/gcj/2006/cjam.cpp
___________________________________________________________________
Name: svn:executable
   + *


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.