Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

做了一天的题，留念一下。。

Posted by juruo_zzt at 2020-03-20 18:18:44 on Problem 3322
```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct node
{
int x,y,sta;
node(int a,int b,int c): x(a),y(b),sta(c) {}
};
int n,m,endx,endy;
char a[510][510];
int book[510][510][3];
const int nxtx[3][4]={{-2,0,1,0},{-1,0,1,0},{-1,0,2,0}};
const int nxty[3][4]={{0,-2,0,1},{0,-1,0,2},{0,-1,0,1}};
const int nxtz[3][4]={{2,1,2,1},{1,0,1,0},{0,2,0,2}};
bool in(int x,int y) {return x>=1 && x<=n && y>=1 && y<=m;}
bool check(node s)
{
int x=s.x,y=s.y,sta=s.sta;
if(a[x][y]=='#') return false;
if(!in(x,y)) return false;
if(~book[x][y][sta]) return false;
if(sta==0)
{
if(a[x][y]=='E') return false;
return true;
}
if(sta==1)
{
if(a[x][y+1]=='#') return false;
if(!in(x,y+1)) return false;
return true;
}
if(sta==2)
{
if(a[x+1][y]=='#') return false;
if(!in(x+1,y)) return false;
return true;
}
return true;
}
int bfs(int stx,int sty,int ststa)
{
queue<node> que;
que.push(node(stx,sty,ststa));
book[stx][sty][ststa]=0;
while(!que.empty())
{
node head=que.front(); que.pop();
int x=head.x,y=head.y,sta=head.sta;
int stp=book[x][y][sta]+1;
for(int i=0;i<4;i++)
{
int tx=x+nxtx[sta][i];
int ty=y+nxty[sta][i];
int tsta=nxtz[sta][i];
if(!check(node(tx,ty,tsta))) continue;
book[tx][ty][tsta]=stp;
que.push(node(tx,ty,tsta));
if(tx==endx && ty==endy && tsta==0) return book[tx][ty][tsta];
}
}
return -1;
}
// 0/1/2 竖/橫躺/竖躺
int main()
{
while(~scanf("%d %d",&n,&m) && n)
{
endx=endy=0;
memset(a,0,sizeof(a));
memset(book,-1,sizeof(book));
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
int ststa=0,stx=0,sty=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='X')
{
a[i][j]='.';
stx=i;
sty=j;
if(a[i+1][j]=='X')
{
ststa=2;
a[i+1][j]='.';
}
else if(a[i][j+1]=='X')
{
ststa=1;
a[i][j+1]='.';
}
else ststa=0;
//					break;
}
if(a[i][j]=='O')
{
endx=i;
endy=j;
a[i][j]='.';
}
}
}
int kkksc03=bfs(stx,sty,ststa);
if(kkksc03!=-1) printf("%d\n",kkksc03);
else puts("Impossible");
}
return 0;
}```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator