P10492 [ICPC 2003 Aizu R] Weather Forecast

题目描述

你是风之神。

通过移动一朵大云，你可以决定天气：云下必定下雨，其他地方阳光普照。

但你是一个仁慈的神：你的目标是给乡间的每个田地带来足够的雨水，给市场和节日带来阳光。小人类用他们贫乏的词汇，只能将这称为“天气预报”。

你负责管理一个名为 Paccimc 的小国家。这个国家由4 × 4 4 \times 44×4的方块区域组成，用它们的编号表示。

你的云的大小为2 × 2 2 \times 22×2，不得越过国家的边界。

给出了一段时间内每个区域的市场和节日的安排。

在该时段的第一天，无论安排如何，在中心区域（6-7-10-11）都会下雨。

在接下来的每一天，你可以将你的云向四个基本方向之一（北、西、南和东）移动1 11或2 22个方格，也可以将其保持在原位。不允许对角线移动。所有移动均发生在一天开始时。

你不应该让一个区域连续一周没有雨水（也就是说，你允许最多连续6 66天没有雨）。你不必在你获得的时间段之外的日子里考虑雨水：也就是说，你可以假设在时间段之前的整个国家都下雨，在它结束后的一天也是如此。

输入格式

输入一个数据集序列，后跟一个仅包含零的终止行。

一个数据集在单独的一行上给出了期间中的天数N NN（不超过365 365365），然后是N NN行，给出了市场和节日的安排。第i ii行给出了第i ii天的安排。它由16 1616个数字组成，要么是0 00要么是1 11，0 00表示正常日，1 11表示市场或节日。数字之间用一个或多个空格分隔。

输出格式

对每个数据集的单行输出，如果你能满足每个人，则输出1 11，否则输出0 00。

【样例解释】

翻译来自于：ChatGPT

输入输出样例 #1

输入 #1

1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0

输出 #1

0 1 0 1

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,a[405][5][5],f[5][5][405][8][8][8][8];intdx[]={-1,0,-2,0,2,0,1,0,0},dy[]={0,-1,0,-2,0,2,0,1,0};intdfs(intx,inty,intday,intex,intsx,intey,intsy){if(f[x][y][day][ex][sx][ey][sy]!=-1)returnf[x][y][day][ex][sx][ey][sy];for(inti=x;i<=x+1;i++)for(intj=y;j<=y+1;j++)if(a[day][i][j]==1)return0;if(ex>=7||sx>=7||ey>=7||sy>=7)return0;if(day==n)return1;intans=0;for(inti=0;i<9;i++){inttx=x+dx[i],ty=y+dy[i];if(1<=tx&&tx<=3&&1<=ty&&ty<=3){inta,b,c,d;if(tx==1&&ty==1)a=0;elsea=ex+1;if(tx==3&&ty==1)b=0;elseb=sx+1;if(tx==1&&ty==3)c=0;elsec=ey+1;if(tx==3&&ty==3)d=0;elsed=sy+1;ans|=dfs(tx,ty,day+1,a,b,c,d);}}if(f[x][y][day][ex][sx][ey][sy]==-1)f[x][y][day][ex][sx][ey][sy]=ans;returnans;}intmain(){while(1){memset(f,-1,sizeof(f)),cin>>n;if(n==0)break;for(inti=1;i<=n;i++)for(intj=1;j<=4;j++)for(intk=1;k<=4;k++)cin>>a[i][j][k];cout<<dfs(2,2,1,1,1,1,1)<<'\n';}}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容