lightoj1046

CODE

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n,m;
struct node
{
        int x,y;
        int dis;
};
char g[15][15];
int ans[15][15];
int x[105],y[105],ncase;
queue<node> q;
int dir[8][2]={1,2,
               1,-2,
               -1,2,
               -1,-2,
               2,1,
               2,-1,
               -2,1,
               -2,-1 };
int cnt;

int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                cnt=0;
                int ans=0x3f3f3f3f;
                cin >> n >> m;
                for(int i=0;i<n;i++)
                {
                        cin >> g[i];
                        for(int j=0;j<m;j++)
                        {
                                if(g[i][j]!='.')
                                {
                                        x[cnt]=i;
                                        y[cnt++]=j;
                                }
                        }
                }
                for(int i=0;i<n;i++)
                        for(int j=0;j<m;j++)
                {
                        int tp[10][10];
                        int vis[10][10];
                        memset(tp,0x3f,sizeof(tp));
                        memset(vis,0,sizeof(vis));
                        q.push((node){i,j,0});
                        vis[i][j]=1;
                        while(q.size())
                        {
                                node cur=q.front();
                                int x=cur.x;
                                int y=cur.y;
                                int dis=cur.dis;
                                tp[x][y]=dis;
                                q.pop();
                                for(int i=0;i<8;i++)
                                {
                                        int cx=x+dir[i][0];
                                        int cy=y+dir[i][1];
                                        if(cx>=0&&cy>=0&&cx<n&&cy<m&&!vis[cx][cy])
                                        {
                                                q.push((node){cx,cy,dis+1});
                                                vis[cx][cy]=1;
                                        }
                                }
                        }
                        int res=0;
                        for(int k=0;k<cnt;k++)
                        {
                                int r=x[k];
                                int c=y[k];
                                if(tp[r][c]==0x3f3f3f3f)
                                {
                                        res=0x3f3f3f3f;
                                        break;
                                }
                                res+=(tp[r][c]-1+g[r][c]-'0')/(g[r][c]-'0');
                                //cout <<k<<' '<<i<<' '<<j<<' '<< res <<endl;
                        }
                        ans=min(ans,res);
                }
                cout << "Case "<<++ncase<<": ";
                if(ans==0x3f3f3f3f)
                        cout <<-1<<endl;
                else    cout << ans <<endl;

        }
        return 0;
}