加载中…
个人资料
淡而很无味
淡而很无味
  • 博客等级:
  • 博客积分:0
  • 博客访问:13,357
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

胜利逃亡--方格取数--玉米地

(2020-09-27 20:16:36)
分类: 动态规划
一)胜利大逃亡(2) 
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢,如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
Input
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图,其中包括:
. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙,对应的门分别为A-J
每组测试数据之间有一个空行。
Output
针对每组测试数据,如果可以成功逃亡,请输出需要多少分钟才能离开,如果不能则输出-1。
Sample Input
4 5 17
@A.B.
a*.*.
*..*^
c..b*

4 5 16
@A.B.
a*.*.
*..*^
c..b*
Sample Output
16
-1

#include "bits/stdc++.h"
using namespace std;
int m,n,t;
char graph[25][25];
bool vis[24][24][1<<10];
int dic[4][2] = {-1,0,1,0,0,-1,0,1};
struct note{
    int x,y,state,time;
}loc;queues;

int bfs(int x,int y){
    while(!s.empty())   s.pop();
    loc.state = 0;
    loc.time = 1;
    loc.x = x;
    loc.y = y;
    s.push(loc);
    while(!s.empty())
    {
        note fa,son;
        fa = s.front();
        s.pop();
        for(int i = 0 ; i < 4 ; i++){
            son.x = fa.x + dic[ i ][ 0 ];
            son.y = fa.y + dic[ i ][ 1 ];
            if(son.x < 1 || son.y < 1|| son.y > n || son.x > m||!vis[son.x][son.y][fa.state]) continue;     //这一行很关键,没有这一行就是MLE
            if(graph[son.x][son.y] == '^')
            {
                if(fa.time == t ) return -1;
                else return fa.time;
            }
            if(graph[son.x][son.y] >='a'&& graph[son.x][son.y] <='z' &&vis[son.x][son.y][fa.state| (1 <<(graph[son.x][son.y]-'a'))])
            {
                son.state = fa.state | (1 <<(graph[son.x][son.y]-'a'));
                son.time = fa.time+1;
                vis[son.x][son.y][son.state] = false;
                s.push(son);
            }
            else if(graph[son.x][son.y]<='Z' && graph[son.x][son.y] >='A' && fa.state & (1 << graph[son.x][son.y]-'A') &&vis[son.x][son.y][fa.state])
            {
                son.state = fa.state;
                son.time = fa.time+1;
                vis[son.x][son.y][son.state] = false;
                s.push(son);
            }
           else if(graph[son.x][son.y]=='.'||graph[son.x][son.y]=='@'&&vis[son.x][son.y][fa.state])
            {
                son.state = fa.state;
                son.time = fa.time + 1 ;
                vis[son.x][son.y][son.state] = false;
                s.push(son);
            }
        }
    }
    return -1;
}

int main(){
    int x,y;
    while(~scanf("%d%d%d",&m,&n,&t))
    {
        getchar();        //吃掉一个换行符
        memset(graph,0,sizeof(graph));
        memset(vis,true,sizeof(vis));
        int ans;
        for(int i = 1 ; i <= m; i++)
        {
            for(int j = 1 ; j <= n ; j++)
            {
                scanf("%c",&graph[i][j]);
                if(graph[i][j]=='@')
                    x = i,y = j;
            }
            getchar();
        }
        ans = bfs(x,y);
        printf("%d\n",ans);
    }
    return 0;
}

二)铺地砖 POJ2411
给你n*m(1<=n,m<=11)的方格矩阵,要求用1*2的多米诺骨牌去填充,问有多少种填充方法。
Sample Input
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
Sample Output

1
0
1
2
3
5
144
51205


using namespace std;
const int INF = 1 << 12 + 10;
long long dp[13][2100];
int n,m;
void dfs(int i,int j,int state,int next);
    
int main(){
while(~scanf("%d%d",&n,&m) && (n+m))
{
if(n > m){
n = n ^ m;
m = m ^ n;
n = n ^ m; 
}
memset(dp,0,sizeof(dp));
dp[1][0] = 1;
for(int j = 1; j <= m; j++) //状态转移 
for(int state = 0; state < (1 << n); state++)
if(dp[j][state] > 0)dfs(0,j,state,0);
printf("%lld\n",dp[m+1][0]); //输出答案 
}
return 0;

void dfs(int i,int j,int state, int next)
{
if(i == n)
{
dp[j+1][next] += dp[j][state];
return;
}
else
{
if((state&(1 << i) )== 0)//当该格子没被覆盖说明可以放一个1*2的木板 
dfs(i+1,j,state,next | (1<< i));
if(i + 1 < n &&(state & (1 << i)) == 0 && (state & (1 << (i+1))) == 0)
dfs(i+2,j,state,next);
if((state & (1 << i)) > 0)//当该格子被覆盖时,说明这个格子什么都不能放 
dfs(i+1,j,state,next);
}
}

三)玉米地 P1879/poj3254
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
农场主John新买了一块长方形的新牧场,这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12),每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。
遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是John不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。
John想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)
输入格式
第一行:两个整数M和N,用空格隔开。
第2到第M+1行:每行包含N个用空格隔开的整数,描述了每块土地的状态。第i+1行描述了第i行的土地,所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块土地不适合种草。
输出格式
一个整数,即牧场分配总方案数除以100,000,000的余数。
输入输出样例
输入 #1复制
2 3
1 1 1
0 1 0
输出 #1复制
9
参考程序一:
const int INF = 1 << 12 + 5;
int   dp[15][INF];
int data[15][15];
int n,m;
void dfs(int i,int j,int state,int next,int flag);

int main(){
while(~scanf("%d%d",&n,&m))
{
for(int i = 1; i <= n; i++)
for(int j = 0; j < m; j++)
scanf("%d",&data[i][j]);
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
for(int i = 0; i < n; i++)
for(int state = 0; state < (1<<m); state++)
if(dp[i][state] > 0) dfs(i,0,state,0,0);
int ans = 0;
for(int state = 0; state < (1<<m); state++)
if(dp[n][state] > 0)
ans=(ans+dp[n][state])0000000;
printf("%d\n",ans);
}
return 0;
}

void dfs(int i,int j,int state,int next,int flag)
{
if(j == m) 
dp[i+1][next] = (dp[i+1][next] + dp[i][state])0000000;
else
{
if(data[i+1][j] == 1 && (state & (1<<j)) == 0 && flag== 0) 
{
if(flag == 0||flag == 1)    //不种玉米 
  dfs(i,j+1,state,next,0);
if(flag == 0) //种玉米 
dfs(i,j+1,state,next | (1<<j),1);
}
else
dfs(i,j+1,state,next,0);
}
}

参考程序二,来源洛谷:
#include
using namespace std;
const int M = 1e9;
int m, n, f[13][4096], F[13], field[13][13];
bool state[4096];
int main(){
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> field[i][j];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            F[i] = (F[i] << 1) + field[i][j];
    int MAXSTATE = 1 << n;
    for (int i = 0; i < MAXSTATE; i++)
        state[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);
    f[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < MAXSTATE; j++)
            if (state[j] && ((j & F[i]) == j))
                for (int k = 0; k < MAXSTATE; k++)
                    if ((k & j) == 0)
                        f[i][j] = (f[i][j] + f[i-1][k]) % M;
    int ans = 0;
    for (int i = 0; i < MAXSTATE; i++)
        ans += f[m][i], ans %= M;
    cout << ans << endl;
    return 0;
}

0

阅读 收藏 转载 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有