T1
低仿机器人
（robo，1s，64M）
题目描述
自从 Dji 推出 robomaster S1 机器人过后，小文就一直缠着爸爸想要一个机器人。没想到爸爸最后竟然带了个低仿 S1--R1 机器人回来。小文哭笑不得，不过低仿就低仿，不玩白不玩，他决定试试这个小机器人的能耐。
小文给这个小机器人布置了 n*m 的场地（场地外用障碍围住），在场地上设置了障碍、水池和靶子。其中，障碍是不可以通过并且无法用水晶弹打掉的，靶子无法通过、但是可以被水晶弹打掉，水池也无法通过、但是水晶弹可以通过水池。
小文检查了一下小机器人，发现它的指令系统很简单。该系统中一共有 6 种指令，指令的使用说明如下：
“FT x” ：该指令表示炮台的 90°转动，其中 x∈[0，1]，x∈Z，并且 0、1 分别表示逆时针和顺时针。
“FF i” ：该指令表示填弹，填弹后弹仓剩余弹量减一，弹夹剩余弹量加一，其中 i∈[0，1]且 i∈Z，i 为 1 表示所填水晶弹为大弹丸，为 0 表示所填水晶弹为小弹丸。
“FE” ：该指令表示发射水晶弹，水晶弹的发射方向同炮台的朝向，发射的水晶弹为最后一个填入弹夹的水晶弹，指令执行后弹夹容量减一。
“WT x” ：该指令表示机器人的 90°转动， 其中 x∈[0，1]，x∈Z， 并且 0、1 分别表示逆时针和顺时针。
“WG y” ：该指令表示机器人前进 y 步，其中 y∈[0，max（m，n）），y∈Z。
“END” ：该指令将返回“Complete”并停机，不同于编译器先编译后运行，END（及其他将造成停机的情况）后的指令均被无视。
现在小文将要开始测试，但是为了避免自己的指令集让小机器人出现错误，小文给了你场地、小机器人的初始状态和指令集并拜托你帮他计算出小机器人的返回内容、停下的位置、打掉的靶子数量以及小机器人的状态。
注意：
（一）弹夹无弹的情况下将跳过 FE 指令，弹仓无相应弹丸的情况下将跳过 FF 指令;
（二）大水晶弹一发打掉靶子，小水晶弹需两发打掉靶子，靶子打掉后变成空地可通过;
（三）小机器人将在以下情况下返回“ERROR”并停机：
（1）在弹夹已满的情况下继续填弹;
（2）撞上障碍（包括未被打掉的靶子）或者撞进水池;
（3）指令后的参数不满足要求（例：“FE 10”）;
（4）无“END”指令;
输入格式
输入文件的第一行为一个正整数 t，表示该题有 t 组数据。
对于每一组数据：
第 1 行为两个正整数 n m
第 2～（n+1）行，每行 m 个正整数，表示地图，其中 1 代表障碍，2 代表靶子，3 代表水池，0 代表空地。
第 n+2 行有 6 个正整数，依次为：机器人横坐标 x 和纵坐标 y，弹夹的容量 a，弹仓内剩余大水晶弹量 b，弹仓内剩余小水晶弹量 c，小文的指令数量 k。（弹夹初始容量默认为 0，炮台和机器人的默认朝向为向上）。
第（n+3）～（n+3+k）行，每行一个指令，指令的正确格式和正确参数见题目描述（数据中无双引号）（不满足要求的参数大小<=10,长度<=3）。
输出格式
输出文件共 t*4 行，其中对于每组数据：
第 1 行输出小机器人的返回内容（“Complete”或“ERROR”，不输出双引号）。
第 2 行输出小机器人停下的位置的横纵坐标（用空格隔开）。
第 3 行输出小机器人打掉的靶子数量 h。
第 4 行依次输出炮台的朝向、机器人的朝向、弹仓剩余大水晶弹量、弹仓剩余小水晶弹量，用空格隔开，其中 0、1、2、3 分别表示上左下右。
若机器人返回“ERROR”后停机，则输出数据为执行错误指令前的数据。（见样例 1）
数据范围
对于 10%的数据，t=1 且输入的指令的参数不会出错。
对于另外 20%的数据，输入的指令的参数不会出错。
对于另外 50%的数据，弹仓只有大弹丸。
对于全部数据，t<=20，n、m<=200，a<=30，b、c<=100，k<=100。
样例输入 1
1
5 5
2 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
4 4 3 1 1 6
WG 4
FT 0
WG 1
FE
END
FF
样例输出 1
ERROR
0 4
0
1 0 1 1
第一眼看上去就是又臭又长的题面...
读完后发现是一个大模拟，就按照他的要求做就好了
“FT x”和”WT x”：这个指令只能进行转动，所以处理起来很轻松，一直记录炮台和机器人本体的方向，然后随着指令转动即可，唯一要检验的就是参数是否符合规则。
“FF i”：这个指令需要讨论一下，以下两种情况该指令不被执行：i==0 且小水晶弹数量为 0、i==1 且大水晶弹数量为 0；注意大弹丸和小弹丸的不同。可以把每一个障碍的生命值设成2，大弹丸使生命值-2，小弹丸使生命值-1
以下两种情况该指令将导致停机并返回”ERROR”：
参数错误、相应水晶弹数量不为 0 且弹夹已满；
其他情况则正常处理，记得记录一下弹丸的大小，发射的时候要用；
“FE”：这个命令不需要检查错误，主要是区分一下发射的是大 or 小水晶弹，前面有靶子的话就相应处理就完事了，没有水晶弹就啥都不干。
“WG y”：这个命令一是注意一下参数不能出错导致”ERROR”，二是注意判断会不会撞到障碍和靶子或者撞进水池导致”ERROR”，都没有问题的话就直接移动到目的点完事。
“END”：看到这个命令直接退出就行。
几个要注意的点：
a.记得记录一下小机器人停机的情况，如果到最后都没有停过机则返回”ERROR”；
b.参数错误有可能是参数的大小不对，也有可能是参数的类型不对如（“FT 0.3”）。建议使用 getline 处理，总之处理参数也不需要多打几行……
c.记得出现过停机情况则之后的所有指令全部无视，所以记得全部读入一下别一不小心直接开始读下一组数据了……
d.大概就这样，总之注意一下题目里的小细节，认真读题就没啥问题了
另外不要用scanf，因为读不了空格之后的东西...亲身体验
还有上一步是指执行指令之前，不是指撞到障碍或者掉水里的上一步...又坑了我一次...
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int xGo[4]={-1,0,1,0}; const int yGo[4]={0,-1,0,1}; int n,m,map[220][220][2]; int x,y,fOri,wOri,maxCilp,totCilp,cilp[32],bigBullet,smallBullet,k,endIf,totTarget; void IN_Map_Robot(); void OutPut(int); int Para(char str[]); void FortCom(char str[]); void WheelCom(char str[]); void EndCom(char str[]); int main() { freopen("robo.in","r",stdin); freopen("robo.out","w",stdout); int t; scanf("%d",&t); while(t--) { IN_Map_Robot(); while(k--) { char str[10]; cin.getline(str,10); if(endIf) continue; if(str[0]=='F') FortCom(str); if(str[0]=='W') WheelCom(str); if(str[0]=='E') EndCom(str); } if(!endIf) OutPut(0); } fclose(stdin); fclose(stdout); return 0; } void IN_Map_Robot() { memset(map,0,sizeof(map)); totCilp=0,fOri=0,wOri=0,endIf=0,totTarget=0; scanf("%d%d",&n,&m); for(int i=0;i<n;++i) for(int j=0;j<m;++j) scanf("%d ",&map[i][j][0]); scanf("%d %d %d %d %d %d\n",&x,&y,&maxCilp,&bigBullet,&smallBullet,&k); } void FortCom(char str[]) { if(str[1]=='T') { int par=Para(str+3); if(par==0) fOri=(fOri+1)%4; else if(par==1) fOri=(fOri+3)%4; else { OutPut(0); return ; } } if(str[1]=='F') { int par=Para(str+3); if((par==0&&smallBullet==0)||(par==1&&bigBullet==0)) return; if(par==0&&totCilp<maxCilp) cilp[++totCilp]=par,smallBullet--; else if(par==1&&totCilp<maxCilp) cilp[++totCilp]=par,bigBullet--; else { OutPut(0); return ; } } if(str[1]=='E') { if(totCilp==0) return ; int nx,ny; for(int i=1;;++i) { nx=x+xGo[fOri]*i,ny=y+yGo[fOri]*i; if(nx<0||nx>=n||ny<0||ny>=m) break; if(map[nx][ny][0]==1||map[nx][ny][0]==2) break; } totCilp--; if(nx<0||nx>=n||ny<0||ny>=m) return ; if(map[nx][ny][0]==1) return ; if(cilp[totCilp+1]||map[nx][ny][1]) { map[nx][ny][0]=0; totTarget++; } else map[nx][ny][1]=1; } } void WheelCom(char str[]) { if(str[1]=='T') { int par=Para(str+3); if(par==0) wOri=(wOri+1)%4; else if(par==1) wOri=(wOri+3)%4; else { OutPut(0); return ; } } else { int par=Para(str+3); int nx=x+xGo[wOri]*par,ny=y+yGo[wOri]*par; if(nx<0||nx>=n||ny<0||ny>=m) { OutPut(0); return ; } else { for(int i=1;i<=par;++i) { nx=x+xGo[wOri]*i,ny=y+yGo[wOri]*i; if(map[nx][ny][0]) { OutPut(0); return ; } } } x=nx,y=ny; } } void EndCom(char str[]) { OutPut(1); } void OutPut(int type) { endIf=1; if(type) printf("Complete\n"); else printf("ERROR\n"); printf("%d %d\n",x,y); printf("%d\n",totTarget); printf("%d %d %d %d\n",fOri,wOri,bigBullet,smallBullet); } int Para(char str[]) { int i,re=0; for(i=0;;++i) { if(str[i]=='.') return 114514; if(str[i]=='\0') break; } i=0; do { re=re*10+(str[i]-'0'); i++; }while(str[i]!='\0'); return re; }
T2
迷路的刺豚（expand,1.5s,64M)
题目描述
有一只名叫小T的刺豚，一大早它妈妈就让它出门买菜。它看见了一只可爱的小海马，一路追着它跑啊跑啊。结果……小T迷路了。但妈妈在家里等得很着急，它要赶紧买完菜回家。
所以！当务之急！它要知道去买菜的路……它记得所有菜店的坐标，也知道它现在的坐标。请你帮帮她，找到一条买完菜的路吧。它已经急得快哭了，它想要买完菜回家。因此它需要你找到一条最短的路买菜。
由于它是一条可以膨胀的刺豚，它喜欢自己大大的体格，因此它希望在路径最短的情况下使自己的体格最大，即在移动时离障碍尽可能远。因为你开着上帝视角，所以你知道小T所在的地图。你能帮它找到一条路吗？
注意：
1、此处的离障碍最远是保证在任何时候、在保证路径最短的情况下离障碍最远。当然小T只需要你保证在每个位置的体格之和尽可能大。
2、不需要考虑小T回家的路
输入格式
第一行两个数，表示小T所在的地图大小和小T的最大体格。
体格为i表示小T会占据(2*i+1)^2个格子。
接下来n行每行m个数字表示地图，其中‘1’表示障碍，'0'表示空地。
接下来一行三个数x,y,p表示小T所在的坐标(x,y) 和菜店数量p 。
接下来p行，第 两个数表示菜店i所在的坐标。
输出格式
输出两个数，表示最短路长度以及每个位置的体格之和。
数据范围
对于20% 的数据，所有菜市位置和小T所在的位置在一条水平直线上。
对于另外30% 的数据，s=0 ，其中20% 的数据还满足n,m<=50
对于另外20%的数据，p=1
对于100%的数据，n,m<=300 ，s<=10 ，p<=15
样例输入1
4 5 3 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 0 0
样例输出1
6 0
样例输入2
4 6 3 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 3 0
样例输出2
7 5
这个题要分步来做
1 对于30%的数据 所有菜市位置和小T所在的位置在一条水平直线上
考虑有部分菜市在小T右边，部分菜市在小T左边。
只有两种遍历情况：向左再向右、向右再向左
而在每个点处的、可行的最大体格是确定的，因此直接累加即可。
最终答案在两种情况中选取一个路径更短的或最短路径相同情况下体格和最大的。
2 对于s=0且n,m<=50的数据
当 s==0时，问题转变为从一个点出发遍历p个点的最短路问题。
最朴素的想法应该是搜索，每次搜索下一步去哪个点。
但搜索的问题在于它考虑了经过每个点的顺序。
实际上经过顺序不会对答案产生影响、经过了哪些点才会有影响。
因为你设的是最短距离，就是说你这个数组存储的东西和顺序无关，只是一个最小值。当然这个最小值是考虑过了顺序之后的。
因此考虑用状压表示哪些点没去过，然后寻找一个没去过的点更新。
定义状态 dis[x][y][s]表示还没去过s 集合中的点，目前在点(x,y) 的最短距离。
可使用bfs更新，复杂度 O(n*m* 2^p)，可解决n,m<=50 的情况。
与旅行商问题很类似吧。
对于s=0的数据
很容易可以发现，dis[x][y][z] 的三维中，s在很多点是不会被更新的，因此这些点处出现了状态冗余。
因此只在p 个点处定义dis ，即状态改为dis[i][s] ，表示在第i 个点处的最短路。
转移时需要利用两个点间的最短路。
最短路可通过O(p) 次bfs预处理得到。
复杂度O(p*n*m+ 2^p *p*p)
4 对于p=1的数据
只有一个目标点，因此只用考虑膨胀问题。
在每一个点都会重新膨胀，因此在每个点处的最大膨胀值其实是固定的，可以预处理
在bfs的时候直接将每个点的膨胀值加入答案即可。
复杂度O(p*n*m+s*s*n*m)
5 对于100%的数据
将3中的bfs部分与4结合，即可得到正解。
复杂度O((p+s*s)*n*m+ 2^p *p*p)
#include <bits/stdc++.h> using namespace std; const int N=505,M=505,K=15; const int dx[4]={0,0,1,-1}; const int dy[4]={1,-1,0,0}; const char* st[4]={"R","L","D","U"}; int Path[(N+M)<<1],n,m,S; int mp[N][M]; void Read_Map() { scanf("%d%d%d",&n,&m,&S); for (int i=0;i<n;++i) for (int j=0;j<m;++j) scanf("%d",&mp[i][j]);//mp=0为可行，否则为障碍 } queue<pair<int,int> >Q; int Path_[K+1][K+1][(N+M)<<1],dist[K+1][K+1],szt[K+1][K+1]; int dis[K][1<<K],sum[K][1<<K]; pair<int,int> pre[K][1<<K]; void Put_Path(int *Path,int &len,int begin,int end) { for (int i=0;i<dist[begin][end];++i) Path[len++]=Path_[begin][end][i]; } bool CoordValid(int x,int y) { return x>=0 && x<n && y>=0 && y<m; } bool CoordValid(int x,int y,int size) { for (int i=-size;i<=size;++i) for (int j=-size;j<=size;++j) if (!CoordValid(x+i,y+j) || mp[x+i][y+j]==1) return 0; return 1; } int Size(int x,int y) { for (int i=S;i>=0;--i) if (CoordValid(x,y,i)) return i; return -1; } int pree[N][M],diss[N][M],sz[N][M]; void FindPath(int *ax,int *ay,int count) { for (int i=0;i<count;++i) { Q.push(make_pair(ax[i],ay[i])); memset(pree,0,sizeof(pree)); memset(diss,0x7f,sizeof(diss)); memset(sz,0,sizeof(sz)); diss[ax[i]][ay[i]]=0; while (!Q.empty()) { pair<int,int> u=Q.front(); Q.pop(); for (int i=0;i<4;++i) { int tx=u.first+dx[i],ty=u.second+dy[i],s=Size(tx,ty); if (s!=-1 && (diss[tx][ty]>diss[u.first][u.second]+1 || (diss[tx][ty]==diss[u.first][u.second]+1 && sz[u.first][u.second]+s>sz[tx][ty]))) { diss[tx][ty]=diss[u.first][u.second]+1; pree[tx][ty]=i; sz[tx][ty]=sz[u.first][u.second]+s; Q.push(make_pair(tx,ty)); } } } for (int j=0;j<count;++j) { dist[i][j]=diss[ax[j]][ay[j]]; szt[i][j]=sz[ax[j]][ay[j]]; // int len=0,nowx=ax[j],nowy=ay[j]; // while (nowx!=ax[i] || nowy!=ay[i]) { // Path_[i][j][len++]=pree[nowx][nowy]; // int px=nowx-dx[pree[nowx][nowy]],py=nowy-dy[pree[nowx][nowy]]; // nowx=px; nowy=py; // } // reverse(Path_[i][j],Path_[i][j]+len); } } } void Planning(int now_x,int now_y,int *aim_x,int *aim_y,int count_aim,int *Path,int &len) { aim_x[count_aim]=now_x; aim_y[count_aim]=now_y; FindPath(aim_x,aim_y,count_aim+1); int Mx=1<<count_aim; for (int i=0;i<=count_aim;++i) for (int j=0;j<Mx;++j) pre[i][j]=make_pair(-1,-1),dis[i][j]=1<<30; for (int i=0;i<count_aim;++i) dis[i][(Mx-1)^(1<<i)]=0,sum[i][(Mx-1)^(1<<i)]=0; for (int i=0;i<count_aim;++i) for (int j=Mx-1;j>=0;--j) for (int k=0;k<count_aim;++k) if (i!=k && !((j>>k)&1) && (dis[i][j]>dis[k][j^(1<<i)]+dist[i][k] || ( dis[i][j]==dis[k][j^(1<<i)]+dist[i][k] && sum[i][j]<sum[k][j^(1<<i)]+szt[i][k] ) )) { dis[i][j]=dis[k][j^(1<<i)]+dist[i][k]; sum[i][j]=sum[k][j^(1<<i)]+szt[i][k]; pre[i][j]=make_pair(k,j^(1<<i)); } int mn=0,v=0; len=0; for (int i=1;i<count_aim;++i) if (dis[i][v]+dist[count_aim][i]<dis[mn][v]+dist[count_aim][mn] || (dis[i][v]+dist[count_aim][i]==dis[mn][v]+dist[count_aim][mn] && sum[i][v]+szt[count_aim][i]>sum[mn][v]+szt[count_aim][mn])) mn=i; printf("%d %d\n",dis[mn][v]+dist[count_aim][mn],sum[mn][v]+Size(now_x,now_y)+szt[count_aim][mn]); /* for (int i=1;i<count_aim;++i) if (dis[i][v]+dist[count_aim][i]<dis[mn][v]+dist[count_aim][mn]) mn=i; Put_Path(Path,len,count_aim,mn); while (pre[mn][v].first!=-1) { pair<int,int> u=pre[mn][v]; Put_Path(Path,len,mn,u.first); mn=u.first; v=u.second; } */ } int main() { freopen("expand.in","r",stdin); freopen("expand.out","w",stdout); Read_Map(); int now_x,now_y,aim_x[K],aim_y[K],count_aim; scanf("%d%d%d",&now_x,&now_y,&count_aim); for (int i=0;i<count_aim;++i) scanf("%d%d",&aim_x[i],&aim_y[i]); int len=0; Planning(now_x,now_y,aim_x,aim_y,count_aim,Path,len); // for (int i=0;i<len;++i) // printf("%s",st[Path[i]]); putchar('\n'); fclose(stdin); fclose(stdout); return 0; } /* input: 4 6 3 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 3 0 output: 7 5 */