白駿2589:宝島

18315 ワード
BFS cpp テキストリンク
https://www.acmicpc.net/problem/2589

1.近接

  • は最終的に2つの最も遠い点の問題であり、「最も長い」距離の問題ではBFSが最も適切である.(一歩一歩移動するので、最長または最短距離を求める場合はBFSが望ましい)
  • 初期地図を入力し、地図の値をBFSで1加算し、最大値を選択すればよい.
  • の総変数値は小さいので,すべてのL値に対してBFSを求めた.入場するたびに初期マップ値がコピーされます.
    • +2 Dアレイのコピーにはcopyが使用されています.
    +初期カウント値を0に設定して解き、0に設定すると他のエラーが発生するため1に設定し、最後に1を削除します.初期カウントとL値の区別が難しいためかもしれません.

    2.私の回答

    #include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m;
int map[51][51];
int input[51][51];
bool visited[51][51];
int maxval = 0;
int dc[4] = { -1,1,0,0 };
int dr[4] = { 0,0,-1,1 };

void BFS(int x, int y) {
	queue<pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(x, y), 1));
	visited[x][y] = true;

	while (!q.empty()) {
		int c = q.front().first.first;
		int r = q.front().first.second;
		int count = q.front().second;
		q.pop();
		if (count > maxval)	maxval = count;

		for (int i = 0; i < 4; i++) {
			int nc = c + dc[i];
			int nr = r + dr[i];
			if (nc >= 0 && nc < n && nr>=0 && nr < m) {
				if (map[nc][nr] ==0&&!visited[nc][nr]) {
					q.push(make_pair(make_pair(nc, nr), count + 1));
					map[nc][nr] = count + 1;
					visited[nc][nr] = true;
				}
			}
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string tem;
		cin >> tem;
		for (int j = 0; j < m; j++) {
			if (tem[j] == 'W')	input[i][j] = -1;
			else if (tem[j] == 0)	input[i][j] = 0;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (input[i][j]==0) {
				copy(&input[0][0], &input[0][0] + 51*51, &map[0][0]);
				memset(visited, false, sizeof(visited));

				BFS(i, j);
			}
		}
	}

	cout << maxval-1<< "\n";
	return 0;
}
    SpringBootでMongoDBをバインドする
    参照カウントの単純な実装