1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int M=128; 5 char a[M][M]; 6 int n,dp[M][M][8]; 7 int dx[]={-1,-1,0,1,1,1,0,-1}; 8 int dy[]={0,1,1,1,0,-1,-1,-1}; 9 bool inside(const int &x,const int &y){10     if(x>=0&&x<n&&y>=0&&y<n) return true;return false;11 }12 int getfar(int x,int y,int dir){13     int res=0;14     while(true){15         x+=dx[dir];16         y+=dy[dir];17         if(!inside(x,y)||a[x][y]==‘#‘) break;18         res++;19     }20     return res;21 }22 int turnleft(int dir){23     return (dir+6)%8;24 }25 int turnright(int dir){26     return (dir+2)%8;27 }28 int solve(int x,int y,int dir){29     int res=1,step=1,left=turnleft(dir),right=turnright(dir);30     while(true){31         x+=dx[dir];32         y+=dy[dir];33         if(!inside(x,y)||a[x][y]==‘#‘) break;34         step++;35         res=max(res,step+dp[x][y][left]);36         res=max(res,step+dp[x][y][right]);37     }38     return res;39 }40 int main(){41     while(~scanf("%d",&n),n){42         for(int i=0;i<n;i++){43             scanf("%s",a[i]);44         }45         for(int i=0;i<n;i++){46             for(int j=0;j<n;j++){47                 for(int k=0;k<8;k++){48                     if(a[i][j]==‘#‘){49                         dp[i][j][k]=-1;50                     }51                     else{52                         dp[i][j][k]=getfar(i,j,k);53                     }54                 }55             }56         }57         int ans=0;58         for(int i=0;i<n;i++){59             for(int j=0;j<n;j++){60                 if(a[i][j]==‘.‘){61                     for(int k=0;k<8;k++){62                         int now=solve(i,j,k);63                         ans=max(ans,now);64                     }65                 }66             }67         }68         printf("%d\n",ans);69     }70     return 0;71 }

 1 #include<cstdio> 2 #include<cstring> 3 #define mt(a,b) memset(a,b,sizeof(a)) 4 #define lrrt int L,int R,int rt 5 #define iall 1,n,1 6 #define imid int mid=(L+R)>>1 7 #define lson L,mid,rt<<1 8 #define rson mid+1,R,rt<<1|1 9 const int M=1000010;10 struct T{11     int cover,lazy;12 }tree[M<<2];13 void build(lrrt){14     tree[rt].cover=2;15     tree[rt].lazy=0;16     if(L==R) return ;17     imid;18     build(lson);19     build(rson);20 }21 void pushdown(int rt){22     if(tree[rt].lazy){23         tree[rt<<1].lazy=tree[rt<<1|1].lazy=tree[rt<<1].cover=tree[rt<<1|1].cover=tree[rt].lazy;24         tree[rt].lazy=0;25     }26 }27 void pushup(int rt){28     tree[rt].cover=tree[rt<<1].cover==tree[rt<<1|1].cover?tree[rt<<1].cover:0;29 }30 void update(int x,int y,int z,lrrt){31     if(x<=L&&R<=y){32         tree[rt].cover=tree[rt].lazy=z;33         return;34     }35     imid;36     pushdown(rt);37     if(mid>=x) update(x,y,z,lson);38     if(mid<y)  update(x,y,z,rson);39     pushup(rt);40 }41 bool vis[32];42 void query(int x,int y,lrrt){43     if(L==R){44         vis[tree[rt].cover]=true;45         return ;46     }47     imid;48     if(x<=L&&R<=y){49         if(tree[rt].cover){50             vis[tree[rt].cover]=true;51             return ;52         }53         pushdown(rt);54         query(x,y,lson);55         query(x,y,rson);56         return ;57     }58     pushdown(rt);59     if(mid>=x) query(x,y,lson);60     if(mid<y)  query(x,y,rson);61 }62 int main(){63     int n,m,x,y,z;64     char op[4];65     while(~scanf("%d%d",&n,&m),n|m){66         build(iall);67         while(m--){68             scanf("%s%d%d",op,&x,&y);69             if(op[0]==‘P‘){70                 scanf("%d",&z);71                 update(x,y,z,iall);72             }73             else{74                 mt(vis,0);75                 query(x,y,iall);76                 bool flag=false;77                 for(int i=1;i<=30;i++){78                     if(vis[i]){79                         if(flag) printf(" ");80                         printf("%d",i);81                         flag=true;82                     }83                 }84                 puts("");85             }86         }87     }88     return 0;89 }

  1 #include<cstdio>  2 #include<cstring>  3 #include<cctype>  4 #include<queue>  5 #define mt(a,b) memset(a,b,sizeof(a))  6 using namespace std;  7 const int M=128;  8 char a[M][M];  9 int n,m; 10 struct Snake{ 11     int x,y; 12 }ts[8]; 13 struct Q{ 14     int step,sta,x,y,snake; 15     friend bool operator <(const Q &a,const Q &b){ 16         return a.step>b.step; 17     } 18 }now,pre; 19 priority_queue<Q> q; 20 bool vis[M][M][1<<9]; 21 int dx[]={0,0,1,-1}; 22 int dy[]={1,-1,0,0}; 23 int getkey(const int &psta,const int &x,const int &y){ 24     int ressta=psta; 25     if(isdigit(a[x][y])){ 26         int his=a[x][y]-‘0‘; 27         his=1<<(his-1); 28         if(his-1==psta){ 29             ressta|=his; 30         } 31     } 32     return ressta; 33 } 34 int bfs(){ 35     int ls=0; 36     for(int i=0;i<n;i++){ 37         for(int j=0;j<n;j++){ 38             if(a[i][j]==‘K‘){ 39                 now.x=i; 40                 now.y=j; 41             } 42             if(a[i][j]==‘S‘){ 43                 ts[ls].x=i; 44                 ts[ls].y=j; 45                 ls++; 46             } 47         } 48     } 49     now.snake=0; 50     now.sta=0; 51     now.step=0; 52     mt(vis,0); 53     vis[now.x][now.y][now.sta]=true; 54     int End=(1<<m)-1; 55     while(!q.empty()) q.pop(); 56     q.push(now); 57     while(!q.empty()){ 58         pre=q.top(); 59         q.pop(); 60         if(a[pre.x][pre.y]==‘T‘&&pre.sta==End) return pre.step; 61         for(int i=0;i<4;i++){ 62             int tx=pre.x+dx[i]; 63             int ty=pre.y+dy[i]; 64             if(tx>=0&&tx<n&&ty>=0&&ty<n&&a[tx][ty]!=‘#‘){ 65                 now.sta=getkey(pre.sta,tx,ty); 66                 if(!vis[tx][ty][now.sta]){ 67                     vis[tx][ty][now.sta]=true; 68                     now.x=tx; 69                     now.y=ty; 70                     now.snake=pre.snake; 71                     if(a[tx][ty]==‘S‘){ 72                         int id=0; 73                         for(int j=0;j<ls;j++){ 74                             if(ts[j].x==tx&&ts[j].y==ty){ 75                                 id=j; 76                                 break; 77                             } 78                         } 79                         if((now.snake>>id)&1){ 80                             now.step=pre.step+1; 81                         } 82                         else{ 83                             now.snake|=(1<<id); 84                             now.step=pre.step+2; 85                         } 86                     } 87                     else{ 88                         now.step=pre.step+1; 89                     } 90                     q.push(now); 91                 } 92             } 93         } 94     } 95     return -1; 96 } 97 int main(){ 98     while(~scanf("%d%d",&n,&m),n|m){ 99         for(int i=0;i<n;i++){100             scanf("%s",a[i]);101         }102         int ans=bfs();103         if(ans==-1) puts("impossible");104         else printf("%d\n",ans);105     }106     return 0;107 }