巨佬
by 艾恩葛朗特 @ 2018-10-22 22:25:31
还真没看出来拿错了__(:з」∠)_
by Rbu_nas @ 2018-10-22 22:26:35
@[Rem°](/space/show?uid=80358) 我也就是看不出来。。。诶
by 塞西莉亚 @ 2018-10-22 22:27:33
好久没做的题目
by かねき けん @ 2018-10-22 22:40:26
@[かねき けん](/space/show?uid=37877) 大佬您帮忙看一下吧。。我dfs一开始的剪枝怎么错了。。
by 塞西莉亚 @ 2018-10-22 22:48:04
QAQ @[Miku初音](/space/show?uid=89820)
by かねき けん @ 2018-10-22 23:11:29
等一下哈
by かねき けん @ 2018-10-22 23:11:46
@[Miku初音](/space/show?uid=89820)
```
#include<bits/stdc++.h>
using namespace std;
int m,n,Max=0x3f3f3f3f;
int Map[100+10][100+10];
int val[100+10][100+10];
int xl[10]={1,0,-1,0};
int yl[10]={0,1,0,-1};
void dfs(int x,int y,int ans,int col,int use){
if(ans>=val[x][y]||x<=0||x>m||y<=0||y>m){
return ;
}
if(x==m&&y==m){
Max=min(Max,ans);
return ;
}
val[x][y]=ans;
for(int i=0;i<4;i++){
int dx=x+xl[i],dy=y+yl[i];
if(col>=0&&Map[dx][dy]>=0){
dfs(dx,dy,ans+(Map[dx][dy]==col?0:1),Map[dx][dy],0);
}
if(col>=0&&Map[dx][dy]<0&&use==0){
dfs(dx,dy,ans+2,col,1);
}
}
}
int main(){
scanf("%d %d",&m,&n);
memset(val,0x3f,sizeof(val));
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
Map[i][j]=-1;
}
}
for(int i=1;i<=n;i++){
int x,y,a;
scanf("%d %d %d",&x,&y,&a);
Map[x][y]=a;
}
dfs(1,1,0,Map[1][1],0);
if(Max==0x3f3f3f3f){
puts("-1");
return 0;
}
printf("%d\n",Max);
return 0;
}
```
by Kiel @ 2018-10-22 23:12:13
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int map[105][105],val[105][105];
struct node{
int x,y,c,v;
};
queue<node>q;
int main() {
int m,n,di[4][2]={0,1,1,0,0,-1,-1,0},ans=0x7f7f7f7f;
memset(map,-1,sizeof(map));
memset(val,0x7f,sizeof(val));
cin>>m>>n;
for(int i=0;i<n;i++){
int x,y,c;
cin>>x>>y>>c;
map[x][y]=c;
}
q.push((node){1,1,map[1][1],0});
val[1][1]=0;
while(!q.empty()){
int x=q.front().x,y=q.front().y,c=q.front().c,v=q.front().v;
if(v>ans){
q.pop();
continue;
}
if(x==m&&y==m){
ans=min(ans,v);
q.pop();
continue;
}
for(int k=0;k<4;k++){
int dx=x+di[k][0],dy=y+di[k][1];
if(dx>0&&dy>0&&dx<=m&&dy<=m){
int bc=map[x][y],dc=map[dx][dy],mv=val[dx][dy],dv;
if(dc>=0&&bc>=0){
dv=v+(dc==bc?0:1);
if(mv>dv){
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}else if(dc<0&&bc>=0){
if(mv>v+2){
q.push((node){dx,dy,bc,v+2});
val[dx][dy]=v+2;
}
}else if(dc>=0&&bc<0){
dv=v+(c==dc?0:1);
if(mv>dv){
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}
}
}
q.pop();
}
if(ans==0x7f7f7f7f){
cout<<"-1"<<endl;
}else {
cout<<ans<<endl;
}
return 0;
}
by King_Sunday @ 2018-10-22 23:13:11
emmmm怎么会这样
by King_Sunday @ 2018-10-22 23:14:18