习题 7-2 uva225（回溯）

时间：2021-05-05 20:41:57

题意：从(0.0)点出发，第一次走一步……第k次走k步，且每次必须转90度，不能走重复的点。求k次后回到出发点的所有情况。按最小字典序从小到大输出。

思路：

把所有坐标+220，保证其是正数，然后搜索。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <algorithm>

typedef long long ll;

using namespace std;

const int inf = 0x3f3f3f3f;

int tx[100];

int ty[100];

int dir[4][2] = {{1,0},{0,1},{0,-1},{-1,0}};

int vis[1000][1000];

char dire[] = {"ensw"};

int all;

struct node

{

    int step;

    int x,y;

    int dir;

};

int n,k;

int ans[200];

bool judge(int i,node a)    //判断是否能走

{

    int x = a.x+dir[i][0]*(a.step+1);

    int y = a.y+dir[i][1]*(a.step+1);

    if(i == 1 || i == 2)

    {

        for(int j = 0; j < k; j++)

        {

            if(tx[j] == x && ty[j] >= y && ty[j] <= a.y && i == 2)

                return true;

            if(tx[j] == x && ty[j] >= a.y && ty[j] <= y && i == 1)

                return true;

        }

    }

    if(i == 0 || i == 3)

    {

        for(int j = 0; j < k; j++)

        {

            if(ty[j] == y && tx[j] >= x && tx[j] <= a.x && i == 3)

                return true;

            if(ty[j] == y && tx[j] >= a.x && tx[j] <= x && i == 0)

                return true;

        }

    }

    return false;

}

void dfs(node a)

{

    if(a.x == 220 && a.y == 220 && a.step == n)

    {

//        printf("%d\n",a.step);

//        for(int i = 0; i < a.step;i++)

//            printf("%d ",ans[i]);

//        printf("\n");

        for(int i = 0; i < a.step; i++)

        {

             printf("%c",dire[ans[i]]);

        }

        printf("\n");

        all++;

        return ;

    }

    if(a.step >= n)

        return;

    for(int i = 0; i < 4; i++)

    {

        if(i == 0 && (a.dir == 3||a.dir == 0))continue;

        if(i == 1 && (a.dir == 2||a.dir == 1))continue;

        if(i == 2 && (a.dir == 1||a.dir == 2))continue;

        if(i == 3 && (a.dir == 0||a.dir == 3))continue;

        if(judge(i,a))

            continue;

        node tt = a;

        ans[a.step] = i;

        tt.x = a.x+dir[i][0]*(a.step+1);

        tt.y = a.y+dir[i][1]*(a.step+1);

        if(vis[tt.x][tt.y])

            continue;

        vis[tt.x][tt.y] = 1;

        tt.dir = i;

        tt.step = a.step + 1;

        dfs(tt);

        vis[tt.x][tt.y] = 0;

    }

    return ;

}

int main()

{

    int cas = 1,T;

    int a,b;

    scanf("%d ",&T);

    while(T--)

    {

        scanf("%d %d ",&n,&k);

        memset(vis,0,sizeof(vis));

        for(int i = 0; i < k; i++)

        {

            scanf("%d %d",&a,&b);

            tx[i] = a+220;

            ty[i] = b+220;

        }

        node cur;

        all = 0;

        cur.x = 220,cur.y = 220,cur.step = 0,cur.dir = -1;

        dfs(cur);

        printf("Found %d golygon(s).\n",all);

        printf("\n");

    }

    return 0;

}

　　

相关文章