hdu5335

这道题目昨天做的时候其实想法啥的都差不多了，，但是就是觉得不太好写。比赛结束后看了下别人的代码，发现他们想法并不和我一样，今天再去找了下，找到一篇跟我想法差不多的，然后参悟了一段时间，终于搞懂了。。如果像我那么想的话，真的不太好写。
题目意思不难理解，有一个n*m的01矩阵，从(1，1)出发，到达(n,m)，每走过一个格子，就写下那个格子里的数字(0或1)，问应该怎么走使得最后形成的数字代表的二进制数最小。
想法应该是这样，先用bfs搜索到所有从起点出发遇到的第一个1，因为之前都是0，前导0是被忽略的。遇到第一个1以后，我们就要求到达终点的步数尽量短了，这样才能使得表示的二进制数最小。所以在这些遇到的第一个1坐标里面，我们要选择n+m-x-y+1最小的，也就是到达终点步数最少的。
筛选出来的到达终点步数最少的点也会有很多个。这时，我们移动其中的每一个点，注意，如果要使得它到达终点的步数最短，那么我们移动的方向只能只向下或者向右。在步数一样时，我们在某一步，我们是否能够移动到0处，如果能，那么就移动到0处 ，否则我们只能移动到1处。重复上述步骤直到到达终点。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#define ONLINE_JUDGE
#define eps 1e-8
#define INF 0x7fffffff
#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define sfs(a) scanf("%s",a)
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define pf(a) printf("%d\n",a)
#define pfI(a) printf("%I64d\n",a)
#define pfs(a) printf("%s\n",a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,num) scanf("%d%d%d",&a,&b,&num)
#define for1(i,a,b) for(int i=(a);i
#define for2(i,a,b) for(int i=(a);i<=b;i++)
#define for3(i,a,b)for(int i=(b);i>=a;i--)
#define MEM1(a) memset(a,0,sizeof(a))
#define MEM2(a) memset(a,-1,sizeof(a))
#define ll __int64
const double PI=acos(-1.0);
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T Min(T a,T b){return atemplate<class T> inline T Max(T a,T b){return a>b?a:b;}
using namespace std;
int n,m,k;
#define M 1000010
struct Node{int x,y;Node(int x,int y){this->x = x;this->y = y;}Node(){}
};
int vis[1010][1010];
int vis1[1010][1010];
char ch[1010];
int mp[1010][1010];
int path[5010];
int flag;
vectorv;  //存储遇到的1点中距离出口最近的
vectorv1,v2; //v1存储能走到的1点或者0点坐标  v2存储能走到的0点坐标
int lenth;      //从遇到的第一个1开始，能走出出口的最小步数
int dir[4][2] = {{1,0},{0,1},{0,-1},{-1,0}}; //前两个方向是前进，后两个方向是后退
bool check(int x,int y){if(x<=0 || x>n || y<=0 || y>m)return false;return true;
}
void bfs(){     //找到所有遇到的第一个1点queue q;memset(vis,0,sizeof vis);Node cur,next;v.clear();cur.x = 1;cur.y = 1;vis[1][1] = 1;q.push(cur);while(!q.empty()){cur = q.front();q.pop();for(int i=0;i<4;i++){next.x = cur.x + dir[i][0];next.y = cur.y + dir[i][1];if(!check(next.x,next.y)) continue;if(vis[next.x][next.y]) continue;if(mp[next.x][next.y]){     //遇到了一个1点，那么计算它与出口的距离lenth = Min(lenth,n+m-next.x-next.y+1);continue;}q.push(next);vis[next.x][next.y] = 1;    //标记与入口相连的所有0格子坐标为已访问过}}
}
void bfs2(){path[1] = 1;        //遇到的第一个为1int cnt = 1;Node cur,next;while(cntint size = (int)v.size();for(int i=0;i//遍历所有遇到的符合条件的第一个1点cur = v[i];for(int j=0;j<2;j++){   //符合条件的1点只能朝着终点前进，以以求最短路径next.x = cur.x+dir[j][0];next.y = cur.y+dir[j][1];if(!check(next.x,next.y) || vis1[next.x][next.y]) continue;else{v1.push_back(next); //v1存放所有可到达的点if(!mp[next.x][next.y])v2.push_back(next); //v2存放可以到达的0点vis1[next.x][next.y] = 1;}}}cnt++;if(v2.empty()){ //如果v2为空，说明所有符合条件的点都不能到达0点，只能到达1点，故将v1赋值给vpath[cnt] = 1;v = v1;}else{          //否则的话，说明有能够到达0点的点，此时，只要将符合条件的0点坐标放入v即可，所代表的二进制数肯定是最小的path[cnt] = 0;v = v2;}}
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
#endifint t;sf(t);while(t--){v.clear();memset(vis1,0,sizeof vis1);memset(vis,0,sizeof vis);sfd(n,m);flag = 0;for(int i=1;i<=n;i++){sfs(ch+1);for(int j=1;j<=m;j++)mp[i][j] = ch[j]-'0';}lenth = n+m-1;  //距离出口最远的距离就是n+m-1if(!mp[1][1])   //如果mp[1][1]不为0，那么我们就找所有第一个相遇的1点bfs();if(!mp[1][1]){for(int i=1;i<=n;i++){int j = n+m-i-lenth+1;  //计算离出口最近的几个点坐标if(j>m || j<=0) continue;if(!mp[i][j]) continue; //for(int k=2;k<4;k++){   //这里的意思就是如果i,j这个点旁边的点都没有被访问，说明它是被1包围的，故它不是我们所说的//遇到的第一个1点，舍弃之int x = i+dir[k][0];int y = j+dir[k][1];if(!check(x,y) || !vis[x][y]) continue;else{v.push_back(Node(i,j)); //如果是遇到的第一个1点，那么就放入队列vis1[i][j] = 1;break;}}}}else{      //如果mp[1][1]为1，那么从(1,1)开始，我们就要尽量缩短到达出口的路程v.push_back(Node(1,1));vis1[1][1] = 1;}if(vis[n][m]){printf("0\n");  //如果在bfs()中已经访问过n,m了，那么说明从入口到出口，有一条全为0的路径}else{bfs2();for(int i=1;i<=lenth;i++)printf("%d",path[i]);printf("\n");}}
return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！