poj 1315 Don't Get Rooked(DFS)

解题思路

题意：

在规模不超过4x4的正方形棋盘上放车，里面设有一些车无法通过的障碍，要在车不能无相攻击的情况下放尽量多的车，问最多可放多少。 车可以水平或者竖直移动任意多个格子，只要前面没有障碍。

简化下，就是同行同列在没有障碍隔开的情况下不能有一个以上的车，问最多可放的车的数量。

 

思路：

据说此题是经典的DFS算法题，当然用DFS做了。

从左往右从上到下搜过去。如果当前可放就设标记，继续搜，当前不可放就不设标记继续搜，回来的时候把设了标记的还原。

hasnexti()返回的是下一个格子的横坐标，如果搜光了返回0，结束。

isok()判断当前可放否。

 

ps：

本来用递归还不是很熟练，写了很久没写出来，后来干脆用了个非递归的DFS水过去了，然后再把非递归改成了现在的递归，不容易啊。可能数据很弱，两种算法时间内存都用一样多。

其实还可以用二分图做。现在去试试~

源程序

 

/*非递归深搜*/

#include <stdio.h>
#include <string.h>
#include <conio.h>
int g[5][5], set[5][5];
int max, count;
int n;
struct point
{
    int x;
    int y;
}points[16];

int isok(struct point p)
{
    int k;
    for(k=p.x; k>0; k--)
    {
        if(set[k][p.y]) //从自己出发往前走，如果在遇到墙之前遇到敌人了，行不通
            return 0;
        if(g[k][p.y])
            break;
    }
    for(k=p.y; k>0; k--)
    {
        if(set[p.x][k]) //从自己出发往上走，如果在遇到墙之前遇到敌人了，不可行
            return 0;
        if(g[p.x][k])
            break;
    }
    return 1; //一直没遇到敌人，可放
}
int hasnexti(int i, int j)
{
    if(j == n)
    {
        if(i == n)
            return 0;
        else
        {
            return i+1;
        }
    }
    else
    {
        return i;
    }
}
int search(int i, int j)
{
    int top, k;
    struct point cur;
    while(g[i][j]) //寻找第一个可放点
    {
        if(k = hasnexti(i, j))
        {
            i = k;
            j = (j+1) % n ? (j+1)%n : n;
        }
        else
            return 0; //找到头都没找到
    }
    set[i][j] = 1;
    top = 1;
    count = 1;
    max = 1;
    points[top].x = i;
    points[top].y = j;
    if(k = hasnexti(i, j)) //找下一个可能可以放的格子，作为当前点
    {
        cur.x = k;
        cur.y = (j+1) % n ? (j+1)%n : n;
    }
    else
        return max;

    while(1)
    {        
        if(!g[cur.x][cur.y] && !set[cur.x][cur.y] && isok(cur)) // 当前点可放，进栈
        {
            top++;
            points[top].x = cur.x;
            points[top].y = cur.y;
            set[cur.x][cur.y] = 1;
            count++;
            max = max > count ? max : count;
        }
        if(k = hasnexti(cur.x, cur.y)) //看下一个
        {
            cur.x = k;
            cur.y = (cur.y + 1) % n ? (cur.y+1)%n : n;
        }
        else //没下一个了，回到之前放车的地方....
        {
            cur.x = points[top].x;
            cur.y = points[top].y;
            top--;
            set[cur.x][cur.y] = 0;
            count--;
            if(k = hasnexti(cur.x, cur.y)) //的下一个点
            {
                cur.x = k;
                cur.y = (cur.y + 1) % n ? (cur.y+1) % n : n;
            }
            else //之前放车的下一个点都没了，
            {
                if(top > 0) //如果之前放车的地方还有他之前放车的地方，就再回去
                {
                    cur.x = points[top].x;
                    cur.y = points[top].y;
                    top--;
                    set[cur.x][cur.y] = 0;
                    count--;
                    cur.x = hasnexti(cur.x, cur.y);
                    cur.y = (cur.y + 1) % n ? (cur.y+1) % n : n;
                }
                else //找不到了，退出
                {
                    return max;
                }
            }
        }        
    }    
}

int main()
{
    int i, j;
    char c;
    freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) && n)
    {
        
        memset(g, 0, sizeof(g));
        for(i=1; i<=n; i++)
        {
            getchar();
            for(j=1; j<=n; j++)
            {
                scanf("%c", &c);
                if(c == '.')
                    g[i][j] = 0;
                else
                    g[i][j] = 1;
            }            
        }
        max = 0;
        count = 0;
        memset(set, 0, sizeof(set));
        max = search(1, 1);
        printf("%d\n", max);
    }
    getch();
    return 0;
}

memory: 156k ;  time:0ms

/*递归算法*/

#include <stdio.h>
#include <string.h>
#include <conio.h>
int g[5][5], set[5][5];
int max, count, prei, prej;
int n;
int isok(int i, int j)

{
    int k;
    for(k=i; k>0; k--)
    {
        if(set[k][j])
            return 0;
        if(g[k][j])
            break;
    }
    for(k=j; k>0; k--)
    {
        if(set[i][k])
            return 0;
        if(g[i][k])
            break;
    }
    return 1;
}
int hasnexti(int i, int j) //下一个坐标
{
    if(j == n)
    {
        if(i == n)
            return 0;
        else
        {
            return i+1;
        }
    }
    else
    {
        return i;
    }
}
void search(int i, int j)
{
    int k;
    if(!g[i][j] && !set[i][j] && isok(i, j))
    {
        set[i][j] = 1;
        count++;
        max = max > count ? max : count;    
        search(i, j);
        set[i][j] = 0;
        count--;
    }
    if(!(k = hasnexti(i, j)))
        return;
    else
    {
        i = k;
        j = (j+1)%n ? (j+1)%n : n;
        if(!g[i][j] && !set[i][j] && isok(i, j))
        {
            set[i][j] = 1;
            count++;
            max = max > count ? max : count;    
            search(i, j);
            set[i][j] = 0;
            count--;
        }        
        search(i, j);
    }
}

int main()
{
    int i, j;
    char c;
    freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) && n)
    {
        
        memset(g, 0, sizeof(g));
        for(i=1; i<=n; i++)
        {
            getchar();
            for(j=1; j<=n; j++)
            {
                scanf("%c", &c);
                if(c == '.')
                    g[i][j] = 0;
                else
                    g[i][j] = 1;
            }            
        }
        max = 0;
        count = 0;
        memset(set, 0, sizeof(set));    
        search(1, 1);
        printf("%d\n", max);
    }
    getch();
    return 0;
}