# 加载中...

• 博客等级：
• 博客积分：0
• 博客访问：13,357
• 关注人气：0
• 获赠金笔：0支
• 赠出金笔：0支
• 荣誉徽章：

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

(2020-09-27 20:16:36)
 分类： 动态规划

Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……

Input

. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J

Output

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;
}

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);
}
}

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想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

2 3
1 1 1
0 1 0

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