本文主要是介绍hihocode 1290 Demo Day(DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#1290 : Demo Day
-
4 8 ....bb.. ........ .....b.. ...bb...
样例输出 -
1
描述
You work as an intern at a robotics startup. Today is your company's demo day. During the demo your company's robot will be put in a maze and without any information about the maze, it should be able to find a way out.
The maze consists of N * M grids. Each grid is either empty(represented by '.') or blocked by an obstacle(represented by 'b'). The robot will be release at the top left corner and the exit is at the bottom right corner.
Unfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can't and keep moving to the bottom until it can't. At the beginning, the robot keeps moving to the right.
rrrrbb.. ...r.... ====> The robot route with broken sensors is marked by 'r'. ...rrb.. ...bb...
While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?
输入
Line 1: N, M.
Line 2-N+1: the N * M maze.
For 20% of the data, N * M <= 16.
For 50% of the data, 1 <= N, M <= 8.
For 100% of the data, 1<= N, M <= 100.
输出
The minimum number of grids to be changed.
题目规定了一开始先向右然后遇到b或到边界就向下 遇到b或边界再向右 问最少才去几次操作可以走到右下角
假设要走到点从上面下来需要的操作是up[i][j] 从左边到右边的操作是l[i][j]
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 10010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int Read()
{char c = getchar();while (c < '0' || c > '9') c = getchar();int x = 0;while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x;
}void Print(int a)
{if(a>9)Print(a/10);putchar(a%10+'0');
}char ch[110][110];
int up[110][110],l[110][110];int Getup(int i,int j)
{int x=up[i-1][j];int y=l[i-1][j];if(ch[i-1][j+1]!='b')y++;//如果向右遇到b则向下 没有就进行一次操作 +1return min(x,y);
}int Getleft(int i,int j)
{int x=up[i][j-1];int y=l[i][j-1];if(ch[i+1][j-1]!='b')x++;return min(x,y);
}int main()
{//fread;int n,m;while(scanf("%d%d",&n,&m)!=EOF){getchar();for(int i=0;i<n;i++){scanf("%s",ch[i]);int len=strlen(ch[i]);ch[i][len]='b';ch[i][len+1]='\0';}for(int i=0;i<=m;i++)ch[n][i]='b';int cnt=0;for(int i=0;i<=m;i++){if(ch[0][i]=='b'){cnt++;}l[0][i]=cnt;up[0][i]=INF;}cnt=0;if(ch[0][1]!='b')cnt++;//很关键 一开始要往右走for(int i=0;i<=n;i++){if(ch[i][0]=='b')cnt++;up[i][0]=cnt;l[i][0]=INF;}for(int i=1;i<n;i++){for(int j=1;j<m;j++){up[i][j]=Getup(i,j);l[i][j]=Getleft(i,j);if(ch[i][j]=='b'){up[i][j]++;l[i][j]++;}}}printf("%d\n",min(up[n-1][m-1],l[n-1][m-1]));}return 0;
}
这篇关于hihocode 1290 Demo Day(DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!