2311 Dessert Witch
#include<stdio.h>
#include<string.h>
char map [9][9];
char next[9][9];
char tMap[9][9];
int dxs[]={ 1, 1, 0,-1,-1,-1, 0, 1};
int dys[]={ 0, 1, 1, 1, 0,-1,-1,-1};
int nx,ny;
void revers(int x,int y,char type,int& revMax){
memcpy(tMap,map,sizeof(map));
int revCount=0;
if(tMap[y][x]!='.')return ;
tMap[y][x]=type;
for(int i=0;i<8;i++){
int dx=dxs[i];
int dy=dys[i];
int tx=x;
int ty=y;
for(int j=0;j<8;j++){
tx+=dx;
ty+=dy;
if(tx<0||tx>7||ty<0||ty>7||map[ty][tx]=='.') break;
if(type==map[ty][tx]){
for(int k=0;k<j;k++){
tx-=dx;
ty-=dy;
revCount++;
tMap[ty][tx]=type;
}
break;
}
}
}
if(revCount>revMax){
revMax=revCount;
memcpy(next,tMap,sizeof(next));
}
}
void saiki(int passCount,char type){
if(passCount>2){
return ;
}else{
memcpy(next,map,sizeof(map));
int revMax=0;
if(type=='o'){
for(int y=0;y<8;y++){
for(int x=0;x<8;x++){
revers(x,y,type,revMax);
}
}
}else{
for(int y=7;y>=0;y--){
for(int x=7;x>=0;x--){
revers(x,y,type,revMax);
}
}
}
memcpy(map,next,sizeof(next));
if(revMax>0){
saiki(0,type=='o'?'x':'o');
}else{
saiki(passCount+1,type=='o'?'x':'o');
}
}
}
int main(){
for(int y=0;y<8;y++)scanf("%s",&map[y]);
saiki(0,'o');
for(int y=0;y<8;y++)printf("%s\n",map[y]);
}
2317 Class Representative Witch
#include<stdio.h>
#include<map>
int main(){
std::map<int,int> points,splits,lens;
std::map<int,int>::iterator it,it1,it2;
int n,m,s,t,p,minV=2000000000,maxV=0;
scanf("%d %d",&n,&m);
while(n--){
scanf("%d %d",&s,&t);
points[s]=t;
minV=std::min(std::min(minV,s),t);
maxV=std::max(std::max(maxV,s),t);
}
while(m--){
scanf("%d",&p);
if(minV>p||maxV<p) continue;
splits[p]=0;
}
long double ans=0;
int no=0;
splits[0]=0;
for(it=splits.begin();it!=splits.end();it++){
splits[(*it).first]=no;
if(no<2){
lens[no]=(*it).first;
}else{
lens[no]=(*it).first+lens[no-2];
it--;
lens[no]-=(*it).first;
it++;
}
//printf(" %d=%d ",no,lens[no]);
no++;
}
splits[maxV+1]=no;
int no1,no2,p1,p2;
for(it=points.begin();it!=points.end();it++){
s=(*it).first;
t=(*it).second;
it1=splits.upper_bound(s);
it2=splits.upper_bound(t);
it1--;
it2--;
no1=(*it1).second;
no2=(*it2).second;
if(s<t){
if(no1==no2){
ans+=t-s;
}else if(no1%2!=no2%2){
it1++;
//printf("A(%d %d %d %d %d %d) ",(*it1).first,s,no2,no1,lens[no2],lens[no1]);
ans+=(*it1).first-s;
ans+=lens[no2]-lens[no1+1];
}else{
it1++;
//printf("B(%d %d %d %d %d %d) ",(*it1).first,(*it2).first,s,t,lens[no2-1],lens[no1]);
ans+=((*it1).first-s)+(t-(*it2).first);
ans+=lens[no2-1]-lens[no1+1];
}
}else{
if(no1==no2){
ans+=s-t;
}else if(no1%2!=no2%2){
//printf("B(%d %d %d %d %d %d) ",(*it1).first,(*it2).first,s,t,lens[no1-1],lens[no2]);
ans+=(s-(*it1).first);
ans+=lens[no1-1]-lens[no2];
}else{
it2++;
ans+=(s-(*it1).first)+((*it2).first-t);
ans+=lens[no1-1]-lens[no2+1];
}
}
}
printf("%.0Lf\n",ans);
}
2320 Infinity Maze
#include<stdio.h>
#include<string.h>
#include<iostream>
int dxs[4]={1,0,-1,0};
int dys[4]={0,1,0,-1};
int h,w;
char map[101][102];
long long int memo[101][102][4];
struct robo{
int muki;
int x,y;
long long int L;
bool move(char map[101][102]){
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dxs[muki];
ny=y+dys[muki];
if(ny<0||h<=ny||nx<0||w<=nx||map[ny][nx]=='#'){
muki=(muki+1)%4;
}else{
break;
}
}
L--;
x=nx;
y=ny;
return true;
}
};
int main(){
while(1){
long long int L;
memset(memo,-1,sizeof(memo));
std::cin>>h>>w>>L;
if(h==0&&w==0&&L==0)break;
robo r;
for(int i=0;i<h;i++){
scanf("%s",map[i]);
for(int j=0;j<w;j++){
char c=map[i][j];
if(c!='.'&&c!='#'){
r.y=i;
r.x=j;
r.L=L;
map[i][j]='.';
if(c=='E')r.muki=0;
if(c=='S')r.muki=1;
if(c=='W')r.muki=2;
if(c=='N')r.muki=3;
memo[i][j][r.muki]=0;
}
}
}
char mukis[10]="ESWN";
bool isLoop=false;
while(1){
//printf("%d %d %c %d\n",r.y,r.x,mukis[r.muki],r.L);
if(r.L<=0||r.move(map)==false||r.L==0){
printf("%d %d %c\n",r.y+1,r.x+1,mukis[r.muki]);
break;
}
if(memo[r.y][r.x][r.muki]==-1){
memo[r.y][r.x][r.muki]=L-r.L;
}else if(memo[r.y][r.x][r.muki]!=-1&&isLoop==false){
r.L=(r.L)%((L-r.L)-memo[r.y][r.x][r.muki]);
isLoop=true;
}
}
}
}
最終更新:2013年01月23日 09:20