BFS沿着0走,记录下最靠近终点的1

然后斜着扫描

Walk Out

2
2 2
11
11
3 3
001
111
101

111
101

/* ***********************************************
Author        :CKboss
Created Time  :2015年08月01日 星期六 20时06分43秒
File Name     :HDOJ5335_2.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef pair<int,int> pII;
const int maxn=1100;

int n,m;
char mp[maxn][maxn];
bool vis[maxn][maxn];

const int dir_x[4]={1,-1,0,0};
const int dir_y[4]={0,0,1,-1};

bool OK(int x,int y)
{
	if(vis[x][y]==true) return false; 
	if((x>=0&&x<n)&&(y>=0&&y<m)) return true;
	return false;
}

bool inside(int x,int y)
{
	if((x>=0&&x<n)&&(y>=0&&y<m)) return true;
	return false;
}

void BFS()
{
	int mx=0;

	queue<pII> q;

	if(mp[0][0]=='0') q.push(make_pair(0,0));
	vis[0][0]=true;

	while(!q.empty())
	{
		pII u=q.front(); q.pop();

		for(int i=0;i<4;i++)
		{
			int x=u.first+dir_x[i];
			int y=u.second+dir_y[i];

			if(OK(x,y)==false) continue;

			vis[x][y]=true;

			if(mp[x][y]=='0')
			{
				q.push(make_pair(x,y));
			}
			else if(mp[x][y]=='1')
			{
				mx=max(mx,x+y);
			}
		}
	}

	if(vis[n-1][m-1]==true)
	{
		putchar(mp[n-1][m-1]);
		putchar(10);
		return ;
	}

	for(int i=mx;i<n+m-1;i++)
	{
		char ch='1';
		for(int x=0;x<n;x++)
		{
			int y=i-x;
			if(inside(x,y)==false||vis[x][y]==false) continue;
			ch=min(ch,mp[x][y]);
		}
		putchar(ch);
		for(int x=0;x<n;x++)
		{
			int y=i-x;

			if(inside(x,y)==false||vis[x][y]==false) continue;
			if(mp[x][y]!=ch) continue;

			if(inside(x+1,y)==true) vis[x+1][y]=true;
			if(inside(x,y+1)==true) vis[x][y+1]=true;
		}
	}
	putchar(10);
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)
			scanf("%s",mp[i]);
		memset(vis,false,sizeof(vis));
		BFS();
	}
    
    return 0;
}

HDOJ 5335 Walk Out 贪心+BFS

原文：http://blog.csdn.net/ck_boss/article/details/47190519