SRM 588 D2 L3:GameInDarknessDiv2,DFS

出典:http://community.topcoder.com/stat?c=problem_statement&pm=12710
DFS検索を採用し、初めて書いた時にアクセスマークを付けるのを忘れてしまい、結果として状態空間は指数関数的に増加し(主に重複する状態が多いため)、まったく結果は算出されず、後にアクセスフラグ配列vを加えると重複する状態にアクセスしないことが保証される.この問題のヒントはDFSを用いて重複する状態にアクセスしないことを必ず覚えておくことであり、時にはそれを忘れやすくなり、アルゴリズムが失敗することになる.
コードは次のとおりです.
 

#include <algorithm>

#include <iostream>

#include <sstream>



#include <string>

#include <vector>

#include <stack>

#include <deque>

#include <queue>

#include <set>

#include <map>



#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>



using namespace std;





/*************** Program Begin **********************/

vector <string> f;

string M;

bool v[2600][50][50];

bool BobWin = false;

void move(int Ax, int Ay, int Bx, int By, int steps)

{

	v[steps][Bx][By] = true;

	if (steps == M.size()) {

		BobWin = true;

		return;

	} else {

		int nAx = Ax;

		int nAy = Ay;

		switch (M[steps]) {

		case 'U':

			nAy = Ay - 1;

			break;

		case 'R':

			nAx = Ax + 1;

			break;

		case 'L':

			nAx = Ax - 1;

			break;

		case 'D':

			nAy = Ay + 1;

			break;

		}

		if (nAx == Bx && nAy == By) {

			return;

		}

		int nBx = Bx;

		int nBy = By;

		//  

		nBx = Bx;

		nBy = By - 1;

		if ( nBy >= 0 && '.' == f[nBy][nBx] && !(nAx == nBx && nAy == nBy) && !v[steps+1][nBx][nBy] ) {

			move(nAx, nAy, nBx, nBy, steps+1);

		}

		//  

		nBx = Bx;

		nBy = By + 1;

		if ( nBy <= f.size() - 1 && '.' == f[nBy][nBx] && !(nAx == nBx && nAy == nBy) && !v[steps+1][nBx][nBy] ) {

			move(nAx, nAy, nBx, nBy, steps+1);

		}

		//  

		nBx = Bx - 1;

		nBy = By;

		if ( nBx >= 0 && '.' == f[nBy][nBx] && !(nAx == nBx && nAy == nBy) && !v[steps+1][nBx][nBy] ) {

			move(nAx, nAy, nBx, nBy, steps+1);

		}

		//  

		nBx = Bx + 1;

		nBy = By;

		if ( nBx <= f[0].size() - 1 && '.' == f[nBy][nBx] && !(nAx == nBx && nAy == nBy) && !v[steps+1][nBx][nBy] ) {

			move(nAx, nAy, nBx, nBy, steps+1);

		}

	}

}



class GameInDarknessDiv2 {

public:

	string check(vector <string> field, vector <string> moves) {

		string res = "";

		f = field;

		int Ax = 0, Ay = 0, Bx = 0, By = 0;

		for (int i = 0; i < f.size(); i++) {

			for (int j = 0; j < f[0].size(); j++) {

				if ('A' == f[i][j]) {

					Ay = i;

					Ax = j;

					f[i][j] = '.';

				} else if ('B' == f[i][j]) {

					By = i;

					Bx = j;

					f[i][j] = '.';

				}

			}

		}

		M = "";

		for (int i = 0; i < moves.size(); i++) {

			M += moves[i];

		}

		BobWin = false;

		memset(v, 0, sizeof(v));

		move(Ax, Ay, Bx, By, 0);

		if (BobWin) {

			return "Bob wins";

		} else {

			return "Alice wins";

		}

	}

};

/************** Program End ************************/