Submission #70063330

---

Source Code Expand

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

int n, m;
vector<vector<char>> map;
unordered_set<string> set;
pair<int, int> d;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int ret = 987654321;

string change1d(vector<vector<char>> v) {
	string tmp = "";
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tmp += v[i][j];
		}
	}
	return tmp;
}

bool check(vector<vector<char>> v) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			if (v[i][j] == '#') return false;
		}
	}
	return true;
}

vector<vector<char>> move(vector<vector<char>> v, int dir) {
	vector<vector<char>> tmp = v;
	if (dir == 0) {
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < m; j++) {
				if (v[i + 1][j] == '#') {
					tmp[i][j] = v[i + 1][j];
				}
			}
		}
		for (int j = 0; j < m; j++) {
			tmp[n - 1][j] = '.';
		}
	}
	else if (dir == 2) {
		for (int i = n - 1; i > 0; i--) {
			for (int j = 0; j < m; j++) {
				if (v[i - 1][j] == '#') {
					tmp[i][j] = v[i - 1][j];
				}
			}
		}
		for (int j = 0; j < m; j++) {
			tmp[0][j] = '.';
		}
	}
	else if (dir == 3) {
		for (int j = m - 1; j > 0; j--) {
			for (int i = 0; i < n; i++) {
				if (v[i][j - 1] == '#') {
					tmp[i][j] = v[i][j - 1];
				}
			}
		}
		for (int i = 0; i < n; i++) {
			tmp[i][0] = '.';
		}
	}
	else if (dir == 1) {
		for (int j = 0; j < m - 1; j++) {
			for (int i = 0; i < n; i++) {
				if (v[i][j + 1] == '#') {
					tmp[i][j] = v[i][j + 1];
				}
			}
		}
		for (int i = 0; i < n; i++) {
			tmp[i][m - 1] = '.';
		}
	}
	return tmp;
}

void bfs() {
	queue<pair<vector<vector<char>>, int>> q;
	q.push({map, 0});
	string tmp = change1d(map);
	set.insert(tmp);
	while (!q.empty()) {
		vector<vector<char>> cur = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (check(cur)) {
			ret = cnt;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int dir = (i + 2) % 4;
			int ny = d.first + dy[dir];
			int nx = d.second + dx[dir];
			if (ny >= 0 && nx >= 0 && ny < n && nx < m) {
				if (cur[ny][nx] == '#') continue;
			}
			vector<vector<char>> next = move(cur, i);
			tmp = change1d(next);
			if(!set.count(tmp)) q.push({ next, cnt + 1 });
		}

	}
	ret = -1;
}

int main() {
	cin >> n >> m;
	map.assign(n, vector<char> (m));
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			map[i][j] = s[j];
			if (map[i][j] == 'T') {
				d = { i, j };
			}
		}
	}
	bfs();
	cout << ret;
}

Submission Info

Compile Error

Main.cpp: In function ‘bool check(std::vector<std::vector<char> >)’:
Main.cpp:29:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   29 |                 for (int j = 0; j < v[i].size(); j++) {
      |                                 ~~^~~~~~~~~~~~~

Judge Result