AOJ1168.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int Weight;
struct Edge{
  int src, dest;
  bool operator < (const Edge &rhs) const {
    return make_pair(src, dest) < make_pair(rhs.src, rhs.dest);
  }
};

typedef set<Edge> Edges;
typedef vector<Edges> Graph;

const double eps = 1e-6;

int W, H;
vector<string> str;
vector<double> le, ri;
vector<vector<int>> pos;

pair<bool,vector<int>> dfs(const Graph &g, int v) {
  vector<int> w;
  for (Edge e : g[v]) {
    pair<bool,vector<int>> r = dfs(g, e.dest);
    if (!r.first) return {false, vector<int>(0)};
    for (int i : r.second) w.push_back(i);
  }
  for (int i : pos[v]) w.push_back(i);
  double sum = 0;
  for (int i : w) sum += i;
  double gp = sum / (double)w.size();
  if (gp < le[v] + eps || gp > ri[v] - eps) return {false,vector<int>(0)};
  return {true, w};
}

void paint(vector<vector<int>> &dat, int i, int j, char from, int to) {
  if (i < 0 || i >= H || j < 0 || j >= W) return;
  if (str[i][j] != from) return;
  str[i][j] = '.';
  dat[i][j] = to;
  int dx[4] = {1, 0, -1, 0};
  int dy[4] = {0, 1, 0, -1};
  REP(k,4) paint(dat, i+dy[k], j+dx[k], from, to);
}

int main() {
  while (cin >> W >> H, H) {
    str.assign(H, "");
    vector<vector<int>> dat(H, vector<int>(W, 0));

    // まずブロックか盤面に何個あるか調べる
    int N = 0;
    REP(i,H) cin >> str[i];
    REP(i,H) REP(j,W)
      if (str[i][j] >= '1' && str[i][j] <= '9')
        paint(dat, i, j, str[i][j], ++N);

    // 各ブロックの着地面の左端と右端を調べる
    le.assign(N, 100.0); ri.assign(N, 0.0);
    REP(i,H) REP(j,W)
      if (dat[i][j] > 0 && (i == H - 1 ||
          (dat[i+1][j] > 0 && dat[i][j] != dat[i+1][j]))) {
        int num = dat[i][j] - 1;
        le[num] = min(le[num], j - 0.5);
        ri[num] = max(ri[num], j + 0.5);
      }

    // 各ブロックの位置と重さを求める
    pos.assign(N, vector<int>(0));
    REP(i,H) REP(j,W)
      if (dat[i][j] > 0) {
        int num = dat[i][j] - 1;
        pos[num].push_back(j);
      }

    // 各ブロックの位置関係からグラフを作る
    Graph g(N);
    REP(i,H-1) REP(j,W)
      if (dat[i][j] > 0 && dat[i+1][j] > 0 && dat[i][j] != dat[i+1][j]) {
        int src = dat[i+1][j] - 1;
        int dest = dat[i][j] - 1;
        g[src].insert((Edge){src, dest});
      }

    // グラフのsourceを求める
    int src = 0;
    REP(j,W) if (dat[H-1][j] > 0) src = dat[H-1][j] - 1;

    pair<bool, vector<int>> res = dfs(g, src);
    cout << (res.first ? "STABLE" : "UNSTABLE") << endl;
  }
  return 0;
}