[白俊1987]アルファベット

問題(コピー)

縦列R格子、横列C格子の表形板があります.碁盤の各段には大文字が書かれていて、左上隅(1行1列)に馬が置かれています.
マルコは上下左右に隣接する4つの格子のうちの1つに移動し、新しく移動した格子のアルファベットは以前のすべての格子のアルファベットと異なる必要があります.つまり、同じ文字が書かれたセルを2回通過することはできません.
左上から、プログラムを作成して、出馬を求めるのはせいぜいいくつかの格を通過することができます.馬が通った車両には左上隅の車両も含まれている.

アイデア

確かにDFSだと思います.次のノードにアクセスするかどうかを決定するには、1つのPATHに対してHISTを持つ必要があるからです.ちょうど並んでサイズも400...DFSでしか解決できないと思います.

ただし、DFSは再帰的に実現される

再帰的な記述を利用すれば、1つのhistでdfsレベルが下がったら書くことができ、上がったら消してから作ることができます.

誤った答え：StackのDFSを使う

スタックを利用してスタックにアクセスするノードと一緒に自分のhistを保存する方法です.18%を超えた.
したがって、candiオブジェクトでは=演算子のdeepcopyが実現される.
深いコピーをしている間にタイムアウトが発生したようです.
dfsで解くのが正しいようです(サイズ別でも問題別でも...)間違ったときは、dfsの他のスタイルを試してみるべきだと思います.
下部にエラーコードを作成

正しいコード(リサイクル可能DFS)

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int r, c;
char tab[20][20];
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };

bool inbox(int i, int j) {
	return i >= 0 && i < r&& j >= 0 && j < c;
}
int max_depth = 0;
void dfs(int ci, int cj,vector<bool> &hist,int depth) {
	max_depth = max(max_depth, depth);

	//child 검사
	for (int k = 0; k < 4; k++) {
		if (inbox(ci + di[k], cj + dj[k])) {
			int child_char = tab[ci + di[k]][cj + dj[k]];
			if (hist[child_char - 'A'] == false) {
				hist[child_char - 'A'] = true;
				dfs(ci + di[k], cj + dj[k], hist, depth + 1);
				hist[child_char - 'A'] = false;
			}
		}
	}
}
int main() {
	cin >> r >> c;
	string inp;
	for (int i = 0; i < r; i++) {
		cin >> inp;
		for (int j = 0; j < c; j++) {
			tab[i][j] = inp[j];
		}
	}
	//재귀적 dfs
	vector<bool> hist(26);
	hist[tab[0][0] - 'A'] = true;
	dfs(0, 0, hist, 1);
	cout << max_depth << endl;
}

スタックを使用するDFS(エラーコード)

#include<iostream>
#include<string>
#include<stack>
#include<memory.h>

using namespace std;
int r, c;
char tab[20][20];
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
//deep copy 구현
struct candi {
	int i, j;
	bool hist[26] = {false};
	void operator=(candi s) {
		this->i = s.i;
		this->j = s.j;
		memcpy(this->hist, s.hist, sizeof this->hist);
	}
	candi() {
		memset(this->hist, 0, sizeof this->hist);
	}
};
bool inbox(int i, int j) {
	return i >= 0 && i < r&& j >= 0 && j < c;
}
int calc_len(bool hist[26]) {
	int sum = 0;
	for (int i = 0; i < 26; i++) {
		if (hist[i]) sum++;
	}
	return sum;
}
/*
void print_candi(candi c) {
	cout << "i : " << c.i << " , j : " << c.j << endl;
	for (int i = 0; i < 26; i++) {
		cout <<i<< ":" << c.hist[i] << " , ";
	}
	cout << endl<<endl;
}
*/
int main() {
	cin >> r >> c;
	string inp;
	for (int i = 0; i < r; i++) {
		cin >> inp;
		for (int j = 0; j < c; j++) {
			tab[i][j] = inp[j];
		}
	}
	stack<candi> s;

	candi cur;
	cur.i = 0;
	cur.j = 0;
	cur.hist[tab[0][0] - 'A'] = true;
	//print_candi(cur);

	s.push(cur);
	int max_len = 0;
	
	while (!s.empty()) {
		cur = s.top();
		s.pop();
		//cout << "current below \n";
		//print_candi(cur);
		for (int k = 0; k < 4; k++) {
			candi child = cur;
			child.i = cur.i + di[k];
			child.j = cur.j + dj[k];
			char child_char = tab[child.i][child.j];
			if (inbox(child.i, child.j) && child.hist[child_char - 'A'] == false) {
				child.hist[child_char - 'A'] = true;
				s.push(child);
				//print_candi(child);
			}
			else {//결산
				max_len = max(max_len, calc_len(cur.hist));
			}
		}
	}
	cout << max_len << endl;
}