1. //1// int main()// {// int n;// cin>>n;// vector<int>t(n,0);// vector< vector<int> >v(n,vector<int>(3,0));// for(int i=0;i<n;i++)// {// cin>>t[i];// for(int j=0;j<3;j++)// {// cin>>v[i][j];// }// }// double M=0.0;// int index=0;// for(int i=0;i<n-1;i++)// {// double s=(v[i+1][0]-v[i][0])*(v[i+1][0]-v[i][0])+(v[i+1][1]-v[i][1])*(v[i+1][1]-v[i][1])+(v[i+1][2]-v[i][2])*(v[i+1][2]-v[i][2]);// double time=t[i+1]-t[i];// ;// if((s/time)>M)// {// M=s/time;// index=i;// }// }// cout<<index+1<<endl;// } 2.各位大佬询问一下为何dfs本地可以跑通 提交就是0% #include<iostream>#include<bits/stdc++.h>using namespace std;//2int TIME=INT_MAX;int t=0;int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};void dfs(int x,int y, int target_x,int target_y,vector<int>&cost,vector< vector<int>> &visited,vector< vector<int>>&g){ int h=g.size(); int w=g[0].size(); if(x==target_x && y==target_y ) { TIME=min(TIME,t); } else { for(int i=0;i<4;i++) { int x1=x+dir[i][0]; int y1=y+dir[i][1]; if(x1>=0 && x1<h && y1>=0 && y1<w && g[x1][y1]==1 && visited[x1][y1]==0)// 違背訪問可以走 { visited[x1][y1]=1; t=t+cost[i]; dfs(x1,y1,target_x,target_y,cost,visited,g); t=t-cost[i]; visited[x1][y1]=0; } } }}int main(){ int count; cin>>count; for(int qwe=0;qwe<count;qwe++) { int h,w,target_x,target_y; cin>>h; cin>>w; vector< vector<int> >visited(h,vector<int>(w,0));//均違背訪問 visited[0][0]=1; cin>>target_x; cin>>target_y; vector<int>cost(4,0); for(int i=0;i<4;i++) cin>>cost[i]; vector< vector<int> >g(h,vector<int>(w,0)); for(int i=0;i<h;i++) for(int j=0;j<w;j++) { char a; cin>>a; if(a=='o') g[i][j]=1; } int t=0; int flag=0;//not go for(int i=0;i<4;i++) { int x1=0+dir[i][0]; int y1=0+dir[i][1]; if(x1>=0 && x1<h && y1>=0 && y1<w && g[x1][y1]==1 && visited[x1][y1]==0) flag=1; } if(flag==1) { dfs(0,0,target_x,target_y,cost,visited,g); cout<<"Case #"<<qwe+1<<": "<<TIME<<endl; } else { cout<<"Case #"<<qwe+1<<": "<<-1<<endl; } TIME=INT_MAX; t=0; }}
