滴滴 算法 821笔试

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;
bool inarea(int i , int j , vector<vector<long>>&res)
{
    return i >= 0 && i < res.size() && j >= 0 && j < res[0].size();
}


int main()
{
    int n; cin >> n;
    if(n == 1)
        {
            cout << 1 << endl;
            return 0;
        }
    vector<vector<long>>res(n,vector<long>(n,0));
    vector<long>dp(n * n,0);
    dp[0] = 1; dp[1] = 1;
    for(int i = 2; i < n * n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
    int count = n * n - 1;
    int i = 0, j = -1;
    vector<pair<int,int>>dir;
    dir.push_back({0,1});dir.push_back({1,0});dir.push_back({0,-1});dir.push_back({-1,0});
    int cur = 0;
    while(count >= 0)
        {
            while(1)
                {
                    if(inarea(i+dir[cur].first,j+dir[cur].second,res) && res[i+dir[cur].first][j+dir[cur].second] == 0)
                        {
                            
                            i += dir[cur].first;
                            j += dir[cur].second;
                            res[i][j] = dp[count];
                            break;
                        }
                    else
                        {
                            cur++;
                            cur = cur % 4;
                        }
                    
                }
            count --;
        }
    for(auto i : res)
        {
            for(auto j : i)
                {
                    cout << j << " ";
                }
            cout << endl;
        }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;

int res = 0;
string target = "CHINA";

bool inarea(vector<vector<char>>&num,int i, int j)
{
    return i >= 0 && i < num.size() && j >= 0 && j < num[0].size();
}

void dfs(vector<vector<char>>&num, int i, int j,vector<vector<char>>&visit,int index)
{
    if(!inarea(num,i,j)) return ;
    if(index == 4 && num[i][j] == target[index])
        {
            res++;
            return;
        }
    if(visit[i][j] == true) return;
    visit[i][j] = true;
    if(num[i][j] == target[index])
        {
            dfs(num,i,j+1,visit,index+1);
            dfs(num,i+1,j,visit,index+1);
            dfs(num,i,j-1,visit,index+1);
            dfs(num,i-1,j,visit,index+1);
        }
}
int main()
{
    int n;
    cin >> n;
    vector<vector<char>>num(n,vector<char>(n,'-1'));
    for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                {
                    cin >> num[i][j];
                }
        }
    for(int i = 0; i < n;i++)
        {
            for(int j = 0; j < n; j++)
                {

                    vector<vector<char>>visit(n,vector<char>(n,false));
                    dfs(num,i,j,visit,0);

                }
        }
    cout << res;

}