这题两种方法不能混,要么vis,要么修改地图
如果第二种是看题解的话，你再看一遍，想一下
by ChenZhengJie @ 2020-11-01 22:34:09
@[ChenZhengJie](/user/308620) 我又vis又修改了地图，过了
by 做梦想Peach @ 2020-11-01 22:35:57
@[做梦想Peach](/user/239030) 发下代码
by ChenZhengJie @ 2020-11-01 22:39:11
你那加了vis和没加vis一样的 dfs递归的时候把vis[x1][y1]置为true,dfs下一层又判断vis[x1][y1]==true?return ; 这不明摆着vis[x1][y1]永远等于true啊
by ChangYiMing @ 2020-11-01 22:39:29
@[ChenZhengJie](/user/308620)
```cpp
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
bool vis[110][110];
int dx[5]={0,0,-1,1},
dy[5]={1,-1,0,0};
int n,m,ans,map[110][110],x,y,z,f[110][110],i,j;
int read () {
int k=0,f=1;
char c=getchar ();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
return k*f;
}
void dfs (int i,int j,int s,bool flag) {
if (i==m&&j==m) {
if (s<ans)
ans=s;
return;
}
if (s>=f[i][j])
return;
f[i][j]=s;
for (int step=0;step<4;step++) {
int nx=i+dx[step];
int ny=j+dy[step];
if (!(nx>=1&&nx<=m&&ny>=1&&ny<=m&&vis[nx][ny]==false))
continue;
if (map[nx][ny]!=0) {
if (map[nx][ny]==map[i][j]) {
vis[nx][ny]=true;
dfs (nx,ny,s,false);
vis[nx][ny]=false;
}
else {
vis[nx][ny]=true;
dfs (nx,ny,s+1,false);
vis[nx][ny]=false;
}
}
else {
if (flag==false) {
vis[nx][ny]=true;
map[nx][ny]=map[i][j];
dfs (nx,ny,s+2,true);
vis[nx][ny]=false;
map[nx][ny]=0;
}
}
}
}
int main () {
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
ans=0x7fffffff;
m=read ();
n=read ();
for (i=1;i<=100;i++)
for (j=1;j<=100;j++)
f[i][j]=0x7fffffff;
for (i=1;i<=n;i++) {
x=read ();
y=read ();
z=read ();
map[x][y]=z+1;
}
dfs (1,1,0,false);
printf ("%d\n",ans==0x7fffffff ? -1 : ans);
return 0;
}
```
by 做梦想Peach @ 2020-11-01 22:39:49
~~看我代码写的多美~~
by 做梦想Peach @ 2020-11-01 22:40:09
@[ChangYiMing](/user/228788) 你换一题，把vis删掉，你看能不能过
by 做梦想Peach @ 2020-11-01 22:40:47
我以上讲的是针对以下这个代码
```cpp
#include <stdio.h>
#include <cstring>
#define ll long long
using namespace std;
int read(){
int a1=0,k1=1;char c1=getchar();
while(c1<'0'||c1>'9'){
if(c1=='-')k1=-1;c1=getchar();
}
while(c1>='0'&&c1<='9'){
a1=a1*10+c1-'0';
c1=getchar();
}
return a1*k1;
}
inline void out1(ll n) {
if(n < 0)
putchar ('-') , n = -n;
if(n > 9)
out1(n / 10);
putchar(n % 10 + '0');
}
inline void out(ll n){
out1(n);printf("\n");
}
int m,n,ans=0x3f3f3f3f;
int a[102][102],f[102][102];
bool vis[102][102];
int dx[8]={0,1,0,-1,0};
int dy[8]={0,0,1,0,-1};
void dfs(int x,int y,int k,int last){
if(x<1||x>m||y<1||y>m)return ;
// if(k>ans)return ;
if(k>=f[x][y])return ;
f[x][y]=k;
if(x==m&&y==m){
if(k<ans)ans=k;
f[x][y]=ans;
return ;
}
// printf("%d %d\n",x,y);
for(int i=1;i<=4;++i){
int x1=x+dx[i],y1=y+dy[i];
if(a[x1][y1]!=0){
if(a[x1][y1]==a[x][y]) vis[x1][y1]=true,dfs(x1,y1,k,0),vis[x1][y1]=false;
else vis[x1][y1]=true,dfs(x1,y1,k+1,0),vis[x1][y1]=false;
}
// else ;
else {
if(last==0){
vis[x1][y1]=true;
a[x1][y1]=a[x][y];
dfs(x1,y1,k+2,1);
a[x1][y1]=0;
vis[x1][y1]=false;
}
}
}
// return f[x][y];
}
int/*signed*/ main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
m=read();n=read();
int x,y,c;
for(int i=1;i<=n;++i){
x=read();y=read();c=read();
a[x][y]=c+1;
}
memset(f,0x7f7f7f,sizeof f);
dfs(1,1,0,0);
if(ans!=0x3f3f3f3f){
printf("%d\n",ans);
}
else {
printf("-1\n");
}
return 0;
}
```
by ChangYiMing @ 2020-11-01 22:40:57
@[ChenZhengJie](/user/308620) 为什么“要么vis”“要么修改地图”要2选1
by ChangYiMing @ 2020-11-01 22:42:53
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n,m;
int mp[105][105];
bool vis[105][105];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ans=2147483647;
bool pd(int i,int j){
return i>=1&&i<=m&&j>=1&&j<=m;
}
int f[105][105];
void dfs(int x,int y,int sum,bool fl,int col){
if(x==m&&y==m){
ans=min(ans,sum);
return;
}
if(sum>=ans)return;
if(f[x][y]<sum)return;
f[x][y]=sum;
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(vis[xx][yy]||!pd(xx,yy))continue;
if(mp[xx][yy]==-1&&fl)continue;
if(col==mp[xx][yy]){
vis[xx][yy]=1;
dfs(xx,yy,sum,0,col);
vis[xx][yy]=0;
}
if(col!=mp[xx][yy]){
if(mp[xx][yy]!=-1){
vis[xx][yy]=1;
dfs(xx,yy,sum+1,0,mp[xx][yy]);
vis[xx][yy]=0;
}
if(mp[xx][yy]==-1){
vis[xx][yy]=1;
dfs(xx,yy,sum+2,1,col);
vis[xx][yy]=0;
}
}
}
}
int main(){
scanf("%d %d",&m,&n);
memset(mp,-1,sizeof(mp));
for(int i=1;i<=n;i++){
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
mp[x][y]=c;
}
memset(f,0x3f,sizeof(f));
dfs(1,1,0,0,mp[1][1]);
if(ans==2147483647)cout<<-1;
else cout<<ans;
}
```
by ChenZhengJie @ 2020-11-01 22:46:36