K. Escape from the Abundoned House
广搜,我们只关心从s到f的路径,无论长短
题意:
一个房间被分为n*m个空间,空间由s,f,‘#’,‘.’组成,只能走‘.’,可以重复走某一个点,走列温度升高1,走行温度降低1,若不能从s到f则输出-1,可以则输出初始温度和结尾温度的差值(初始为0).
思路
如果能走到,答案应该是两点??x和▲y的差值。但既然可以重复走某个点,即当存在列或行可以走的时候,可以重复走以减少温度的差值(走回去再走回来,减少的值一定是2的倍数,所以答案只可能是1或0),可是当只有列或者行时,就不行了,答案即为原来的数。
#include
using namespace std;
char a[1005][1005];
typedef pairPII;
int vis[1005][1005];
#define fi first
#define se second
signed main()
{
PII st,end;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='s')
{
st.fi=i;
st.se=j;
}
else if(a[i][j]=='f')
{
end.fi=i;
end.se=j;
}
}
}
queueque;
que.push(st);
vis[st.fi][st.se]=1;
int is_x=0,is_y=0; //是否只在x和y方向上移动,若只在一个方向上移动,则不会发生降温或者升温
int flag=0; //可以到达终点
int d1[]={1,0,-1,0};
int d2[]={0,1,0,-1};
while(que.size())
{
PII temp=que.front();
que.pop();
for(int i=0;i<4;i++)
{
int x=temp.fi+d1[i];
int y=temp.se+d2[i];
if(1<=x&&x<=n&&1<=y&&y<=m&&a[x][y]!='#'&&vis[x][y]==0)
{
if(d1[i]!=0) is_x=1;
if(d2[i]!=0) is_y=1;
que.push({x,y});
vis[x][y]=1;
if(x==end.fi&&y==end.se)
{
flag=1;//可以到达
}
}
}
}
if(flag)
{
int ans=abs(-abs(end.se-st.se)+abs(end.fi-st.fi)); //确定最小差异
if(is_x&&is_y)
{
if(ans%2) //小细节
{
cout<<1;
}else
{
cout<<0;
}
}else
{
cout<