依图科技笔试

//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;
// }

#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;
    }
}