依图科技笔试
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;
//2
int 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;
}
} 
