OpenJudge

ac code

  • Diana
    Diana 18.2.11 回复

    用时比较长8ms

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #include<algorithm>
    #include<string>
    using namespace std;

    #define N 13
    char alphabet[26] = { 'A','B','C' ,'D' ,'E' ,'F' ,'G' ,'H' ,'I' ,'J' ,'K' ,'L' ,'M' ,'N' ,'O' ,'P' ,'Q' ,'R' ,'S' ,'T' ,'U' ,'V' ,'W' ,'X' ,'Y' ,'Z' };
    int route[N][N];
    int p, q,n,i,flag,found;
    string str;
    int a[8][2] = { { -1,-2 },{ 1,-2 },{ -2,-1 },{ 2,-1 },{ -2,1 },{ 2,1 },{ -1,2 },{ 1,2 } };

    bool dfs(int s, int t)
    {
    flag--;
    route[s][t] =1;
    if (flag == 0) return 1;
    for (int k = 0; k < 8; k++)
    {
    int ss, tt;
    ss = s + a[k][0]; tt = t + a[k][1];
    if (ss< p&&ss>-1&& tt > -1&& tt<q && route[ss][tt] == 0)
    {
    route[ss][tt] = 1;
    if (dfs(ss, tt))
    {
    str = alphabet[tt] + to_string(ss+1)+str; return 1;
    }
    route[ss][tt] = 0;
    }
    }
    flag++;
    route[s][t] = 0;
    return 0;
    }

    int main() {
    cin >> n;
    int s, t;
    for (i = 0; i < n; i++)
    {
    cin >> p >> q;
    if (p == 1 && q == 1)
    {
    cout << "Scenario #" << i+1 << ":" << endl << "A1" << endl << endl;
    continue;
    }
    if (p == 1 || q == 1)
    {
    cout << "Scenario #" << i+1 << ":" << endl << "impossible" << endl << endl;
    continue;
    }
    found = 0;
    for (t = 0; t < q; t++)
    {
    if (found == 1) break;
    for (s = 0; s < p; s++)
    {
    for (int ss = 0; ss < p; ss++)
    for (int tt = 0; tt < q; tt++)
    route[ss][tt] = 0;
    flag = p * q;
    str = "";
    if (dfs(s, t))
    {
    str= alphabet[t] + to_string(s+1) + str;
    cout << "Scenario #" << i+1 << ":" << endl << str << endl << endl; found = 1; break;
    }
    }
    }
    if (!found) cout<< "Scenario #" << i+1 << ":" << endl << "impossible" << endl << endl;
    }

    return 0;
    }

想要评论吗?

注册OpenJudge账号,如果您已经注册,请先登入