死循环还交?你不T谁T
by qseer @ 2018-10-23 22:06:29
是否使用了法术要在dfs中记录,因为你不能连续两次施法
by qseer @ 2018-10-23 22:20:50
你可以参考下我的
```c
#include<stdio.h>
#include<cstring>
using namespace std;
const int inf=0x3ffffff;
int fx[4]={-1,0,1,0};
int fy[4]={0,1,0,-1};
int f[110][110];
int mp[110][110];
int m,n,ans=inf;
void dfs(int x,int y,int sum,bool magic)
{
if(x<1 || y<1 || x>m || y>m) return ;
if(!mp[x][y]) return ;
if(sum>=f[x][y]) return ;
f[x][y]=sum;
if(x==m && y==m) {
if(sum<ans) ans=sum;
return ;
}
for(int i=0;i<4;++i)
{
int nx=x+fx[i];
int ny=y+fy[i];
if(mp[nx][ny])
{
if(mp[nx][ny]==mp[x][y])
dfs(nx,ny,sum,false);
else dfs(nx,ny,sum+1,false);
}
else if(!mp[nx][ny] && !magic)
{
mp[nx][ny]=mp[x][y];
dfs(nx,ny,sum+2,true);
mp[nx][ny]=0;
}
}
}
int main()
{
memset(f,0x7f,sizeof(f));
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
mp[x][y]=c+1;
}
dfs(1,1,0,false);
if(ans==inf) printf("-1");
else printf("%d",ans);
return 0;
}
```
by qseer @ 2018-10-23 22:21:39