白駿2210ディジタルジャンプボード(BFS)

2373 ワード
アルゴリズム#アルゴリズム# C テキストリンク
この問題の場合は多すぎて、n=5の形で与えられたのかもしれません.
6文字でつなげるときは、すべての場合に個数を計算しますが、重複が多いのでsetを使います.△計算が繰り返される問題は、まずsetが考えられますが、ジャンプが多い場合はBFSで解決する方法が考えられます.
#include <iostream>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

queue<int> que;
string n;
int map[5][5];
int mx[] = { 1,-1,0,0 };
int my[] = { 0,0,-1,1 };
set<string> s;

void bfs(int x, int y) {
	queue<tuple<int, int , string>> que;
	que.push({ x, y, to_string(map[x][y]) });

	while (!que.empty()) {
		tie(x,y,n) = que.front();
		que.pop();

		 for (int i = 0; i < 4; i++) {
			 int dx = mx[i] + x;
			 int dy = my[i] + y;
			 if (dx >= 5 || dy >= 5 || dx < 0 || dy < 0)	continue;
			
			 string input = n + to_string(map[dx][dy]);
			 if (input.length() == 6)
				 s.insert(input);
			 else
				 que.push({ dx,dy,input });
		 }
		 
	}
}

int main(void) {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			bfs(i, j);
		}
	}
	cout << s.size() << endl;

}
座標x,y,mapを表すにはtupleを用いることが望ましい[x][y].
ページ上部に移動
TIL defaultPropsとprops.children