2206번-벽 부수고 이동하기

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#define X first
#define Y second
using namespace std;

int n, m;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
string board[1005];
vector<pair<int, int>> wall;
queue<pair<int, int>> q;
vector<int> dis;
int vis[1005][1005];

int bfs() {
	q.push({ 0,0 });
	for (int i = 0; i < n; i++)fill(vis[i], vis[i] + m, 0);
	vis[0][0] = 1;
	while (!q.empty()) {
		pair<int,int> cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.X+dx[i];
			int ny = cur.Y+dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (board[nx][ny] != '0' || vis[nx][ny]>0)continue;
			q.push({ nx,ny });
			vis[nx][ny] = vis[cur.X][cur.Y] + 1;
		}
	}
	return vis[n-1][m-1];
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == '1')wall.push_back({ i,j });
		}
	}
	int res = bfs();
	if (res != 0) {
		dis.push_back(res);
	}
	
	for (int i = 0; i < wall.size(); i++) {
		int nx = wall[i].X;
		int ny = wall[i].Y;
		board[nx][ny] = '0';
		res = bfs();
		if (res != 0) {
			dis.push_back(res);
		}
		board[nx][ny] = '1';
	}
	if (dis.size() == 0) {
		cout << -1;
	}
	else {
		cout << *min_element(dis.begin(),dis.end());
	}
}

위의 방법은 시간 초과가 나온다. 모든 벽을 돌면서 bfs를 하는것이 문제인듯..

그리고 vis의 자료형을 bool로 해서 계속 오류가 났었다..ㅎㅎ제발 꼼꼼하게 확인하쟈~