hdu 5335 Walk Out bfs 2015 Multi-University Training Contest 4 09

題意：從（1,1）走到（n，m）時經過的01串二進制的值最小。

首先确定從（1,1）走到矩陣中的任意一格（i，j），需要走i+j-2步，那麼盡可能的走0且盡早的走0肯定是最優的。是以對于每個相同步數x，可以确定的是走x步能過走到的點，考慮到影響結果的走法 ：x步的走下一個x+1步的結果，要麼是0，要麼是1.那麼如果有0的話肯定選0,這種走法，那就将其加進隊列，否則若在x+1步走一個0都沒遇到，就将是以的x+1的走法加進隊列進行疊代即可。确定了走的方法，再來看起點，很明顯，隻要從（1,1）這個點bfs到裡終點最近的點，也就是離（1,1）最遠的點（即i+j盡可能大）即可。

下附幾組測試資料

#include <bits/stdc++.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <time.h>
#include <vector>
#include <cstdio>
#include <string>
#include <iomanip>
///cout << fixed << setprecision(13) << (double) x << endl;
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define ls rt << 1
#define rs rt << 1 | 1
#define pi acos(-1.0)
#define eps 1e-8
#define Mp(a, b) make_pair(a, b)
#define asd puts("asdasdasdasdasdf");
typedef long long ll;
//typedef __int64 LL;
const int inf = 0x3f3f3f3f;
const int N = 1010;

int n, m;
struct node{
	int x, y;
	bool operator < ( const node &rhs ) const {
		if( x != rhs.x )
			return y < rhs.y;
		return x < rhs.x;
	}
};

char c[N][N];
queue <node> q;
vector <node> v;
string ans;
bool vis[N][N];
int dir[4][2] = {
	1, 0, -1, 0, 0, 1, 0, -1
};

int main()
{
	int tot;
	scanf("%d", &tot);
	while( tot-- ) {
		scanf("%d%d", &n, &m);
		for( int i = 1; i <= n; ++i )
			scanf("%s", c[i]+1);
		if( n == m && n == 1 && c[1][1] == '1' ) {
			puts("1");
			continue;
		}
		memset( vis, 0, sizeof( vis ) );
		bool inq = 0;
		while( !q.empty() )	q.pop();
		node tmp;
		tmp.x = tmp.y = 1;
		if( c[1][1] == '0' ) {
			q.push(tmp);
			vis[1][1] = 1;
			inq = 1;
		}
		while( !q.empty() ) {
			node now = q.front();
			q.pop();
			for( int i = 0; i < 4; ++i ) {
				int x = now.x + dir[i][0];
				int y = now.y + dir[i][1];
				if( x > n || x == 0 || y > m || y == 0 )
					continue;
				if( vis[x][y] || c[x][y] == '1' )
					continue;
				vis[x][y] = 1;
				node nxt;
				nxt.x = x, nxt.y = y;
				q.push( nxt );
				if( x+y >= tmp.x+tmp.y ) {
					tmp.x = x;
					tmp.y = y;
				}
			}
			if( tmp.x >= n && tmp.y >= m )
				break;
		}
		if( tmp.x >= n && tmp.y >= m ) {
			printf("0\n");
			continue;
		}
		ans = "";
		for( int i = 1; i <= n; ++i ) {
			for( int j = 1; j <= m; ++j ) {
				if( vis[i][j] && i+j == tmp.x + tmp.y ) {
					node u;
					u.x = i, u.y = j;
					q.push( u );
				}
			}
		}
		if( !inq ) {
			q.push( tmp );
			ans += '1';
			vis[1][1] = 1;
		}
		v.clear();
		while( 1 ) {
			bool OK = 0;	//下一個是否出現0
			while( !q.empty() ) {
				node now = q.front();
				q.pop();
				node n1, n2;
				n1.x = n2.x = now.x;
				n1.y = n2.y = now.y;
				n1.x++, n2.y++;
				if( n1.x >= 1 && n1.x <= n && n1.y >= 1 && n1.y <= m ) {
					if( !OK ) {
						if( !vis[n1.x][n1.y] ) {
							if( c[n1.x][n1.y] == '0' ) {
								OK = 1;
								v.clear();
								v.push_back( n1 );
							}
							else 
								v.push_back( n1 );
							vis[n1.x][n1.y] = 1;
						}
					}
					else {
						if( !vis[n1.x][n1.y] && c[n1.x][n1.y] == '0' ) {
							v.push_back( n1 );
							vis[n1.x][n1.y] = 1;
						}
					}
				}
				if( n2.x >= 1 && n2.x <= n && n2.y >= 1 && n2.y <= m ) {
					if( !OK ) {
						if( !vis[n2.x][n2.y] ) {
							if( c[n2.x][n2.y] == '0' ) {
								OK = 1;
								v.clear();
								v.push_back( n2 );
							}
							else
								v.push_back( n2 );
							vis[n2.x][n2.y] = 1;
						}
					}
					else {
						if( !vis[n2.x][n2.y] && c[n2.x][n2.y] == '0' ) {
							v.push_back( n2 );
							vis[n2.x][n2.y] = 1;
						}
					}
				}
			}
			int sz = v.size();
			for( int i = 0; i < sz; ++i )
				q.push( v[i] );
			if( q.empty() )	break;
			if( OK )
				ans += '0';
			else
				ans += '1';
			v.clear();
		}
		cout << ans << endl;
	}
	return 0;
}
/*
5 5
11101
00100
01000
01011
11111
5 5
00011
11101
11011
11111
11101
5 5
00011
11011
00011
01011
11011
*/