Wang Xifeng's Little Plot http://acm.hdu.edu.cn/showproblem.php?pid=5024
预处理出每个点八个方向能走的最远距离，然后枚举起点，枚举方向，每走一步都要枚举左转和右转的情况，因为预处理好了，所以可以直接算出来。
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=;
char a[M][M];
int n,dp[M][M][];
int dx[]={-,-,,,,,,-};
int dy[]={,,,,,-,-,-};
bool inside(const int &x,const int &y){
if(x>=&&x<n&&y>=&&y<n) return true;return false;
}
int getfar(int x,int y,int dir){
int res=;
while(true){
x+=dx[dir];
y+=dy[dir];
if(!inside(x,y)||a[x][y]=='#') break;
res++;
}
return res;
}
int turnleft(int dir){
return (dir+)%;
}
int turnright(int dir){
return (dir+)%;
}
int solve(int x,int y,int dir){
int res=,step=,left=turnleft(dir),right=turnright(dir);
while(true){
x+=dx[dir];
y+=dy[dir];
if(!inside(x,y)||a[x][y]=='#') break;
step++;
res=max(res,step+dp[x][y][left]);
res=max(res,step+dp[x][y][right]);
}
return res;
}
int main(){
while(~scanf("%d",&n),n){
for(int i=;i<n;i++){
scanf("%s",a[i]);
}
for(int i=;i<n;i++){
for(int j=;j<n;j++){
for(int k=;k<;k++){
if(a[i][j]=='#'){
dp[i][j][k]=-;
}
else{
dp[i][j][k]=getfar(i,j,k);
}
}
}
}
int ans=;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(a[i][j]=='.'){
for(int k=;k<;k++){
int now=solve(i,j,k);
ans=max(ans,now);
}
}
}
}
printf("%d\n",ans);
}
return ;
}
A Corrupt Mayor's Performance Art http://acm.hdu.edu.cn/showproblem.php?pid=5023
成段更新。
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
#define lrrt int L,int R,int rt
#define iall 1,n,1
#define imid int mid=(L+R)>>1
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
const int M=;
struct T{
int cover,lazy;
}tree[M<<];
void build(lrrt){
tree[rt].cover=;
tree[rt].lazy=;
if(L==R) return ;
imid;
build(lson);
build(rson);
}
void pushdown(int rt){
if(tree[rt].lazy){
tree[rt<<].lazy=tree[rt<<|].lazy=tree[rt<<].cover=tree[rt<<|].cover=tree[rt].lazy;
tree[rt].lazy=;
}
}
void pushup(int rt){
tree[rt].cover=tree[rt<<].cover==tree[rt<<|].cover?tree[rt<<].cover:;
}
void update(int x,int y,int z,lrrt){
if(x<=L&&R<=y){
tree[rt].cover=tree[rt].lazy=z;
return;
}
imid;
pushdown(rt);
if(mid>=x) update(x,y,z,lson);
if(mid<y) update(x,y,z,rson);
pushup(rt);
}
bool vis[];
void query(int x,int y,lrrt){
if(L==R){
vis[tree[rt].cover]=true;
return ;
}
imid;
if(x<=L&&R<=y){
if(tree[rt].cover){
vis[tree[rt].cover]=true;
return ;
}
pushdown(rt);
query(x,y,lson);
query(x,y,rson);
return ;
}
pushdown(rt);
if(mid>=x) query(x,y,lson);
if(mid<y) query(x,y,rson);
}
int main(){
int n,m,x,y,z;
char op[];
while(~scanf("%d%d",&n,&m),n|m){
build(iall);
while(m--){
scanf("%s%d%d",op,&x,&y);
if(op[]=='P'){
scanf("%d",&z);
update(x,y,z,iall);
}
else{
mt(vis,);
query(x,y,iall);
bool flag=false;
for(int i=;i<=;i++){
if(vis[i]){
if(flag) printf(" ");
printf("%d",i);
flag=true;
}
}
puts("");
}
}
}
return ;
}
Saving Tang Monk http://acm.hdu.edu.cn/showproblem.php?pid=5025
集齐m把钥匙，就可以拯救唐僧，没集齐也可以从他身上踩过去，拿钥匙必须从小到大拿，蛇只要杀一次，所以要记录钥匙的状态和蛇是否被杀的状态。bfs。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=;
char a[M][M];
int n,m;
struct Snake{
int x,y;
}ts[];
struct Q{
int step,sta,x,y,snake;
friend bool operator <(const Q &a,const Q &b){
return a.step>b.step;
}
}now,pre;
priority_queue<Q> q;
bool vis[M][M][<<];
int dx[]={,,,-};
int dy[]={,-,,};
int getkey(const int &psta,const int &x,const int &y){
int ressta=psta;
if(isdigit(a[x][y])){
int his=a[x][y]-'';
his=<<(his-);
if(his-==psta){
ressta|=his;
}
}
return ressta;
}
int bfs(){
int ls=;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(a[i][j]=='K'){
now.x=i;
now.y=j;
}
if(a[i][j]=='S'){
ts[ls].x=i;
ts[ls].y=j;
ls++;
}
}
}
now.snake=;
now.sta=;
now.step=;
mt(vis,);
vis[now.x][now.y][now.sta]=true;
int End=(<<m)-;
while(!q.empty()) q.pop();
q.push(now);
while(!q.empty()){
pre=q.top();
q.pop();
if(a[pre.x][pre.y]=='T'&&pre.sta==End) return pre.step;
for(int i=;i<;i++){
int tx=pre.x+dx[i];
int ty=pre.y+dy[i];
if(tx>=&&tx<n&&ty>=&&ty<n&&a[tx][ty]!='#'){
now.sta=getkey(pre.sta,tx,ty);
if(!vis[tx][ty][now.sta]){
vis[tx][ty][now.sta]=true;
now.x=tx;
now.y=ty;
now.snake=pre.snake;
if(a[tx][ty]=='S'){
int id=;
for(int j=;j<ls;j++){
if(ts[j].x==tx&&ts[j].y==ty){
id=j;
break;
}
}
if((now.snake>>id)&){
now.step=pre.step+;
}
else{
now.snake|=(<<id);
now.step=pre.step+;
}
}
else{
now.step=pre.step+;
}
q.push(now);
}
}
}
}
return -;
}
int main(){
while(~scanf("%d%d",&n,&m),n|m){
for(int i=;i<n;i++){
scanf("%s",a[i]);
}
int ans=bfs();
if(ans==-) puts("impossible");
else printf("%d\n",ans);
}
return ;
}
end