/*    一个矩形的屋子里有一个人，他可以踩黑格子，但是不能踩红格子，    他现在站在一个黑格子上，告诉你房间的布局，    这个人可以向上下左右四个方向移动，问这个人最多能到达的格子数*/#include <cstdio>#include <cstring>using namespace std;int W,H,ans,vis[35][35];char mp[35][35];const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};bool check(int x,int y){    if(vis[x][y])return 0;    if(mp[x][y]==‘.‘&&x&&y&&x<=H&&y<=W)return 1;    return 0;}void dfs(int x,int y){    vis[x][y]=1;ans++;    for(int i=0;i<4;i++){        if(check(x+dx[i],y+dy[i]))dfs(x+dx[i],y+dy[i]);    }return;}int main(){    while(~scanf("%d%d",&W,&H),W+H){        ans=0; memset(vis,0,sizeof(vis));        for(int i=1;i<=H;i++)scanf("%s",mp[i]+1);        for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)        if(mp[i][j]==‘@‘)dfs(i,j);        printf("%d\n",ans);    }return 0;}

/*    颜色相同且相邻的块属于同一个果园，求果园的总个数*/#include <cstdio>#include <cstring>using namespace std;int W,H,ans,vis[105][105];char mp[105][105];const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};bool check(int x,int y,char c){    if(vis[x][y])return 0;    if(mp[x][y]==c&&x&&y&&x<=H&&y<=W)return 1;    return 0;}void dfs(int x,int y,char c){    vis[x][y]=1;    for(int i=0;i<4;i++){        if(check(x+dx[i],y+dy[i],c))dfs(x+dx[i],y+dy[i],c);    }return;}int main(){    while(~scanf("%d%d",&H,&W),W+H){        ans=0; memset(vis,0,sizeof(vis));        for(int i=1;i<=H;i++)scanf("%s",mp[i]+1);        for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)        if(!vis[i][j]){ans++;dfs(i,j,mp[i][j]);}        printf("%d\n",ans);    }return 0;}

/*    给出十个小球排成一列，从两个出口出去，问能否做到将十个球按一定分配，    使得两个出口出来的球标号都是递增*/#include <cstdio>int T,a[10];void solve(){    for(int i=0;i<(1<<10);i++){        int pre1=0,pre2=0,flag=1;        for(int j=0;j<10;j++){            if((1<<j)&i){                if(a[j]<pre1){flag=0;break;}                pre1=a[j];            }else{                if(a[j]<pre2){flag=0;break;}                pre2=a[j];            }        }if(flag){puts("YES");return;}    }puts("NO"); return;}int main(){    scanf("%d",&T);    while(T--){        for(int i=0;i<10;i++)scanf("%d",a+i);        solve();    }return 0;}

/*    将一块石头从起点滚到终点，一次必须要滚到碰到石头才会停下来，    而碰到的石头会破碎，如果十步内能到终点则输出步数，否则输出无解*/#include <cstdio>#include  <algorithm>using namespace std;int mp[25][25],ans=0,W,H;const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};bool check(int x,int y){    if(mp[x][y]%2==0&&x&&y&&x<=H&&y<=W)return 1;    return 0;}bool in(int x,int y){    if(x&&y&&x<=H&&y<=W)return 1;    return 0;}void dfs(int x,int y,int d){    if(d>=10)return;    for(int i=0;i<4;i++){        int nx=x,ny=y,flag=0;        while(check(nx+dx[i],ny+dy[i])){            nx+=dx[i],ny+=dy[i];flag=1;        }if(in(nx+dx[i],ny+dy[i])){            if(mp[nx+dx[i]][ny+dy[i]]==3){ans=min(ans,d+1);return;}            if(flag){                mp[nx+dx[i]][ny+dy[i]]=0;                dfs(nx,ny,d+1);                mp[nx+dx[i]][ny+dy[i]]=1;            }        }    }}int main(){    while(~scanf("%d%d",&W,&H),W+H){        ans=11;        for(int i=1;i<=H;i++){            for(int j=1;j<=W;j++){                scanf("%d",&mp[i][j]);            }        }        for(int i=1;i<=H;i++){            for(int j=1;j<=W;j++){                if(mp[i][j]==2)dfs(i,j,0);            }        }if(ans>10)puts("-1");        else printf("%d\n",ans);    }return 0;}

/*    求从起点开始依次到1，2，……，N，的总距离的最小值*/#include <cstdio>#include <queue> #include <cstring>using namespace std;const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};int W,H,T,ans=0,v[1005][1050];char mp[1005][1005];struct data{int x,y;}st,en,P[15];bool check(data x){    return(x.x&&x.y&&x.x<=H&&x.y<=W&&mp[x.x][x.y]!=‘X‘&&v[x.x][x.y]==-1);}int bfs(data st,data en){    queue<data> Q;    data nx;    for(int i=1;i<=H;i++)        for(int j=1;j<=W;j++)v[i][j]=-1;    Q.push(st);     v[st.x][st.y]=0;    while(Q.size()){        data px=Q.front();        Q.pop();        if(px.x==en.x&&px.y==en.y)break;        for(int i=0;i<4;i++){            nx.x=px.x+dx[i];            nx.y=px.y+dy[i];            if(check(nx)){                Q.push(nx);                v[nx.x][nx.y]=v[px.x][px.y]+1;            }        }        }return v[en.x][en.y];}int main(){    scanf("%d%d%d",&H,&W,&T);    for(int i=1;i<=H;i++)scanf("%s",mp[i]+1);    for(int i=1;i<=H;i++)for(int j=1;j<=W;j++){        if(mp[i][j]<=‘9‘&&mp[i][j]>=‘1‘){            int c=mp[i][j]-‘0‘;            P[c].x=i;P[c].y=j;        }else if(mp[i][j]==‘S‘){            st.x=i;st.y=j;        }    }    for(int i=1;i<=T;i++){        en.x=P[i].x;en.y=P[i].y;        ans+=bfs(st,en);        st.x=en.x;st.y=en.y;    }printf("%d\n",ans);    return 0;}

/*    告诉你流星砸下来的时间和砸的位置，每次流星砸下来会影响周边五个格子    被影响到的地方将不能再通行，问能到达安全地点的最短时间*/#include <cstdio>#include <algorithm>#include <climits>using namespace std;const int N=305,inf=INT_MAX; int t,h,n,mp[N][N],vis[N][N],x,y,tim;int mx[4]={0,0,1,-1},my[4]={1,-1,0,0};struct data{int x,y,t;}q[N*N];void bfs(){    vis[0][0]=t=h=1;    if(mp[0][0]==inf){puts("0");return;}    while(t<=h){        x=q[t].x,y=q[t].y,tim=q[t++].t;        for(int i=0;i<4;i++){            int nx=x+mx[i],ny=y+my[i];            if(nx<0||ny<0||vis[nx][ny]||tim+1>=mp[nx][ny])continue;            if(mp[nx][ny]==inf){printf("%d\n",tim+1);return;}            q[++h].x=nx;q[h].y=ny;q[h].t=tim+1;vis[nx][ny]=1;        }    }puts("-1");}int main(){    for(int i=0;i<N;i++)for(int j=0;j<N;j++)mp[i][j]=inf;    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d%d%d",&x,&y,&tim);        mp[x][y]=min(mp[x][y],tim);        for(int j=0;j<4;j++){            int nx=x+mx[j],ny=y+my[j];            if(nx<0||ny<0)continue;            mp[nx][ny]=min(mp[nx][ny],tim);        }    }return bfs(),0;}

/*    七数码问题，将标号1到7的块通过向空位的移动来复原    由于操作可逆，直接通过从终态开始搜索的方法，    将到达每种状态需要的时间记录下来*/#include <queue>#include <iostream>#include <algorithm>#include <string>#include <map> using namespace std;int dx[]={1,-1,4,-4};map<string,int>M;void bfs(){    queue<string> Q;    Q.push("01234567");    M["01234567"]=1;    while(Q.size()){        string x=Q.front();        Q.pop();        int nx=0;        for(int i=0;i<8;i++)if(x[i]==‘0‘)nx=i;        for(int i=0;i<4;i++){            if(nx+dx[i]>=0&&nx+dx[i]<8){                if(nx==3&&i==0||nx==4&&i==1)continue;                string s=x;                swap(s[nx],s[nx+dx[i]]);                if(!M[s]){Q.push(s);M[s]=M[x]+1;}            }        }    }}int x;int main(){    bfs();    while(cin>>x){        string s;        s+=x+‘0‘;        for(int i=1;i<8;i++)cin>>x,s+=x+‘0‘;        cout<<M[s]-1<<endl;    }return 0;}

/*    给出不重复的数位，将其全部用上组成两个数，使得其差最小，    输出这个最小差值*/#include <cstdio>#include <algorithm>#include <climits>using namespace std;int a[10],n,T;char c;int main(){    scanf("%d",&T);getchar();    while(T--){        for(n=0;(c=getchar())!=‘\n‘;)if(c!=‘ ‘)a[n++]=c-‘0‘;        if(n==1)printf("%d\n",a[0]);        else if(n==2)printf("%d\n",abs(a[1]-a[0]));        else{            while(a[0]==0)next_permutation(a,a+n);              int ans=INT_MAX,mid=(n+1)>>1;              do{                  if(a[mid]){                      int x=a[0],y=a[mid];                      for(int i=1;i<mid;i++)x=x*10+a[i];                      for(int i=mid+1;i<n;i++)y=y*10+a[i];                      if(ans>abs(x-y))ans=abs(x-y);                  }              }while(next_permutation(a,a+n));              printf("%d\n",ans);          }    }return 0;}

/*    求一个排列使得其不断地进行邻项相加，最后得到的数为给出的数字*/#include <cstdio>#include <algorithm>using namespace std;int a[10],b[10],n,s;int main(){    scanf("%d%d",&n,&s);    for(int i=0;i<n;i++)a[i]=i+1;    do{        for(int i=0;i<n;i++)b[i]=a[i];        for(int i=n-1;i;i--){            for(int j=0;j<i;j++)b[j]=b[j+1]+b[j];        }            if(b[0]==s){            printf("%d",a[0]);            for(int i=1;i<n;i++)printf(" %d",a[i]);            puts(""); break;        }    }while(next_permutation(a,a+n));    return 0;}

/*    可以翻转行或者列，使得最终状态1最多*/#include <cstdio>#include <algorithm>#include <bitset>using namespace std;int R,C,b,ans;bitset<10000> a[10];bool tmp;void dfs(int k){    if(k==R){        int tmp=0;        for(int j=0;j<C;j++){            int t=0;            for(int i=0;i<R;i++)t+=a[i][j];            tmp+=max(t,R-t);        }ans=max(ans,tmp);        return;    }dfs(k+1);    a[k].flip();    dfs(k+1);}int main(){    while(scanf("%d%d",&R,&C),R+C){        for(int i=0;i<R;i++)            for(int j=0;j<C;j++)scanf("%d",&b),a[i][j]=b;         ans=0;dfs(1);        printf("%d\n", ans);    }return 0;}

/*    求在图中任选起点随意走六步能产生的不同的序列的个数*/#include <cstdio>#include <algorithm>using namespace std;const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};int mp[1000000],a[6][6],ans=0;int check(int x,int y){return(x&&y&&x<6&&y<6);}void dfs(int x,int y,int d,int num){    if(d==6){if(!mp[num]){mp[num]=1;ans++;}return;}    num=num*10+a[x][y];    for(int i=0;i<4;i++){        int nx=x+dx[i],ny=y+dy[i];        if(check(nx,ny))dfs(nx,ny,d+1,num);    }}int main(){    for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)scanf("%d",&a[i][j]);    for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)dfs(i,j,0,0);    printf("%d\n",ans);    return 0;}