程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5335 Walk Out（Bfs搜索字典序最小的最短路）

HDU 5335 Walk Out（Bfs搜索字典序最小的最短路）

編輯：關於C++

題意:nXm的地圖, 問通過四個方向從(1,1)走到（1000,1000）所經過的最小二進制序列是多少，忽略前綴0.

思路：首先如果起點為0，那麼我們bfs搜索和起點0聯通的為0的連通塊，這樣我們第一步肯定是從與這個連通塊相鄰的且與重點最近的地方出發。

將所有可能起點加入隊列，在bfs一遍找到字典序最小的那條路就是答案，

在這裡可以用兩個vector類型容器，一個是q2存儲所有節點值存為0的結點，

另一個q3存儲節點值為1的結點。

那麼如果q2不為空那麼也就是有可以走零，那麼就從這裡面選，否則從q3中選。

ps：下午比賽時各種doubi，先是dfs無懸念超時....然後改成把求字典序的那個dfs改成了bfs結果re訪問非法.......改了後結果爆棧.........最後改了一發覺得肯定對了然而mle了......

直到比賽結束也沒發現為啥mle了，寫了三個半小時要哭了..........回來後發現是因為最開始搜索連通塊時我是每次訪問結點時才置vis為1而不是每次添加結點時就置vis為1，這樣每次會添加很多重復結點肯定會mle...........哭暈在廁所，本來可以ac的還是基礎不扎實........任重道遠

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
using namespace std;  

//const int maxn = 100 + 5;
//const int INF = 0x3f3f3f3f;
bool G[1005][1005];
bool vis[1005][1005];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
bool vis2[1005][1005];
vector > qq;
bool path[2005];
int leng;
int n, m; 
void bfs2() {
	queue > q;
	q.push(make_pair(1, 1));
	vis[1][1] = 1;
	while(!q.empty()) {
		pair t = q.front(); q.pop();
		int i = t.first, j = t.second;
		for(int k = 0; k < 4; k++) {
			int u = i + dx[k], v = j + dy[k];
			if(u < 1 || u > n || v < 1 || v > m || vis[u][v]) continue;
			if(G[u][v]) {
				leng = min(leng, n+m-u-v+1);
				continue;
			}
			q.push(make_pair(u, v));
			vis[u][v] = 1;
		}
	}
}
vector > q2, q3;
void bfs() {
	path[1] = 1;
	int cnt = 1;
	while(cnt < leng) {
		q2.clear(); q3.clear();
		int sz = qq.size();
		for(int fuck = 0; fuck < sz; fuck++) {
			pair t = qq[fuck];
			int i = t.first, j = t.second;
			for(int k = 2; k < 4; k++) {
				int u = i + dx[k], v = j + dy[k];
				if(u < 1 || u > n || v < 1 || v > m || vis2[u][v]) continue;
				else {
					q2.push_back(make_pair(u, v));
					if(!G[u][v]) q3.push_back(make_pair(u, v));
					vis2[u][v] = 1;				
				}
			}
		}
		cnt++;
		if(q3.empty()) {
			qq = q2;
			path[cnt] = 1;
		}
		else  {
			path[cnt] = 0;
			qq = q3;
		}
	}
}
char str[1005];
int main() {
//	freopen(input.txt, r, stdin);
	int t; cin >> t;
	while(t--) {
		memset(vis, 0, sizeof(vis));
		memset(vis2, 0, sizeof(vis2));
		qq.clear();
		cin >> n >> m;
		for(int i = 1; i <= n; i++) {
			scanf(%s, &str);
			int len = strlen(str);
			for(int j = 0; j < len; j++) {
				if(str[j] == '1') G[i][j+1] = 1;
				else G[i][j+1] = 0;
			}
		}
		leng = n + m - 1;
		if(!G[1][1]) bfs2();
		//cout << leng << endl;
		if(!G[1][1]) for(int i = 1; i <= n; i++) {
			int j = n + m - leng + 1 - i;
			if(j > m || j < 1) continue;
			if(!G[i][j]) continue;
			for(int k = 0; k < 2; k++) {
				int u = i + dx[k], v = j + dy[k];
				if(u < 1 || u > n || v < 1 || v > m || !vis[u][v]) continue;
				else {
					qq.push_back(make_pair(i, j));
				//	cout << i <<   << j << endl;
					vis2[i][j] = 1;
					break;
				}
			}
		}
		else qq.push_back(make_pair(1, 1)), vis2[1][1] = 1;
		if(!vis[n][m]) {
			bfs();
			for(int i = 1; i <= leng; i++) printf(%d, path[i]);
		}
		else printf(0);
		puts();	
	}
	return 0;
}