HDU 5335——Walk Out——————【贪心】
Walk Out
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1292 Accepted Submission(s): 239
An explorer gets lost in this grid. His position now is (1,1), and he wants to go to the exit. Since to arrive at the exit is easy for him, he wants to do something more difficult. At first, he'll write down the number on position (1,1). Every time, he could make a move to one adjacent position (two positions are adjacent if and only if they share an edge). While walking, he will write down the number on the position he's on to the end of his number. When finished, he will get a binary number. Please determine the minimum value of this number in binary system.
For each testcase, the first line contains two integers n and m (1≤n,m≤1000). The i-th line of the next n lines contains one 01 string of length m, which represents i-th row of the maze.
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int INF=0x3f3f3f3f;
int vis[maxn][maxn];
int Map[maxn][maxn];
int way[2*maxn];
int f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m,k;
struct NODE{
int x,y;
};
queue<NODE>Q;
stack<NODE>S;
int BFS(){
NODE st,tmp;
while(!Q.empty()){
st=Q.front();
Q.pop();
int xx,yy;
for(int i=0;i<4;i++){
xx=st.x+f[i][0];
yy=st.y+f[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&(!vis[xx][yy])&&Map[xx][yy]==0){
if(xx==n&&yy==m)
return -1;
tmp.x=xx,tmp.y=yy;
vis[xx][yy]=1;
Q.push(tmp);
}
}
}
}
bool check(int x,int y){
int xx,yy;
for(int i=0;i<4;i++){
xx=x+f[i][0];
yy=y+f[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==1){
return true;
}
}
return false;
}
void Find1(int typ){
while(!S.empty())
S.pop();
while(!Q.empty())
Q.pop();
int maxs=-INF;
NODE st,tmp; if(typ==0){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(Map[i][j]==1){
if(check(i,j)){ if(i+j>maxs){
maxs=i+j;
}
st.x=i,st.y=j;
vis[i][j]=2;
S.push(st);
}
}
}
}
}else{
st.x=1,st.y=1;
vis[1][1]=2;
maxs=2;
S.push(st);
}
if(S.empty()==0)
way[k++]=1;
while(!S.empty()){
st=S.top();
S.pop();
if(st.x+st.y==maxs){
Q.push(st);
}
}
while(1){
int flag=0;
while(!Q.empty()){
st=Q.front();
Q.pop();
if(st.x==n&&st.y==m){
return ;
}
int xx,yy;
for(int i=0;i<2;i++){
xx=st.x+f[i][0];
yy=st.y+f[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&(!vis[xx][yy])){
if(Map[xx][yy]==0){
flag=1;
}
tmp.x=xx,tmp.y=yy;
vis[xx][yy]=2;
S.push(tmp);
}
}
}
if(flag==1){
way[k++]=0;
while(!S.empty()){
st=S.top();
S.pop();
if(Map[st.x][st.y]==0){
Q.push(st);
}
}
}else{
way[k++]=1;
while(!S.empty()){
st=S.top();
S.pop();
Q.push(st);
}
}
}
}
int main(){
int t;
char str[1020];
scanf("%d",&t);
while(t--){
k=0;
memset(vis,0,sizeof(vis));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",str+1);
for(int j=1;j<=m;j++){
Map[i][j]=str[j]-'0';
}
}
if(n==m&&n==1&&Map[1][1]==0){
printf("0\n");continue;
}
if(Map[1][1]==0){
NODE st;
st.x=1,st.y=1;
vis[1][1]=1;
while(!Q.empty())
Q.pop();
Q.push(st);
if(BFS()==-1) {
printf("0\n");
continue;
}
Find1(0);
}
else{
Find1(1);
}
for(int i=0;i<k;i++){
printf("%d",way[i]);
}printf("\n");
}
return 0;
}
/*
50
3 3
001
111
101 55
1 2
01 */
最新文章
- Oracle基础——学习笔记
- MDI窗体容器、权限设置
- Android开发-API指南- Calendar Provider
- 我是面试官--";自我介绍";
- 分享一个解析XML成为php数组的方法
- Salesforce 小知识:大量“子记录”的处理方法
- menu
- Python3:几行代码实现阶乘
- vue常考面试题
- mysql兼容emoji表情存取
- jquery的jsonp的使用
- mysql 修改文件记录:
- mysql快速生成truncate脚本清空数据库表记录
- spring cloud 学习
- [转载]MACD 各周期指标状态
- 问题2:input、textarea、submit 宽度设置为100%,但显示宽度不一致
- java语言编程入门
- 连接mysql提示Establishing SSL connection without server&#39;s identity verification is not recommended错误
- [Big Data] Week4B (Basic)
- java poi处理新版xlsx后缀的excel