Go: ///
// File:  0558.go
// Author: ymiyamoto
//
// Created on Sun Mar  4 20:58:45 2018
//
package main

import (
	"fmt"
	"strconv"
	"strings"
)

type pos struct {
	x, y int
}

var H, W, N int
var graph [][]string

func wfs(p pos, index int) (int, pos) {
	var q []pos
	dists := make([][]int, H)
	for i := range dists {
		dists[i] = make([]int, W)
	}

	q = append(q, p)
	for len(q) > 0 {
		p := q[0]
		dist := dists[p.x][p.y]
		q = q[1:]

		for _, d := range []pos{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
			x := p.x + d.x
			y := p.y + d.y
			if 0 <= x && x < H && 0 <= y && y < W && graph[x][y] != "X" && dists[x][y] == 0 {
				dists[x][y] = dist + 1
				q = append(q, pos{x, y})
			}
		}
	}

	for i := range graph {
		for j := range graph[i] {
			if graph[i][j] == strconv.Itoa(index) {
				return dists[i][j], pos{i, j}
			}
		}
	}

	panic("not found")
}

func main() {
	fmt.Scan(&H, &W, &N)

	var start pos

	graph = make([][]string, H)
	for i := range graph {
		var s string
		fmt.Scan(&s)
		graph[i] = strings.Split(s, "")
		for j := range graph[i] {
			if graph[i][j] == "S" {
				start.x = i
				start.y = j
			}
		}
	}

	count := 0
	for i := 1; i <= N; i++ {
		c, s := wfs(start, i)
		start = s
		count += c
	}

	fmt.Println(count)
}

C++: #include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct PP{
	int x;
	int y;
	int Z;
	int c;
};
char s[1002][1002],C[11]={"0123456789"};
int D[1002][1002];
int A[1002][1002],d;
int main(){
	PP S;
	queue<PP> P;
	int  w,h;
	int d=0,i=0,j=0,l=-1;
	int x[4]={ 1, 0,-1,0};
	int y[4]={ 0 ,1,0,-1};
	scanf("%d %d %d",&h,&w,&d);
	memset(A,0,sizeof(A));
   memset(D,0,sizeof(D));
		for(i=0;i<h;i++){
		scanf("%s",s[i]);
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
		if(s[i][j]=='S'){
			S.x=j;
			S.y=i;
			S.Z=0;
			S.c=1;
			P.push(S);
		}
		}
	}
	while(1){
		l++;
		
		if(l==4) {
			l=0;
			P.pop();
		}
		S=P.front();
		A[S.y][S.x]=1;
		S.x+=x[l];
		S.y+=y[l];
		S.Z++;
		if(A[S.y][S.x]==1||s[S.y][S.x]=='X'||S.y==h||S.x==w||S.x==-1||S.y==-1){
		continue;
		}
		if(s[S.y][S.x]=='.'){}
		else{
			if(C[S.c]==s[S.y][S.x]){
				S.c++;
				if(S.c==d+1){
				break;
				}
				while(!P.empty()){
				P.pop();
				
				}
			memset(A,0,sizeof(A));
			l=-1;
			}

		} 
		P.push(S);
	}
	printf("%d\n",S.Z);
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

const int map_max = 1000;
char m[map_max + 5][map_max + 5];
int book[map_max + 5][map_max + 5];
int next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, h, k;
int tim = 0;
int startx, starty;


struct node
{
    int x;
    int y;
    int time;
};

void read_in()
{
    cin >> n >> h >> k;
    getchar();

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < h; j++) {
            scanf("%c", &m[i][j]);
            if(m[i][j] == 'S')
                startx = i, starty = j;
        }
        getchar();
    }
}

bool judge(node t)
{
    if(t.x < 0 or t.x > n or t.y < 0 or t.y > h)
        return false;
    if(book[t.x][t.y]) return false;
    if(m[t.x][t.y] == 'X') return false;

    return true;
}

void bfs(char aim)
{
    queue<node> q;
    q.push(node{startx, starty, tim});

    while(!q.empty()) {
        node now = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            node temp{now.x + next[i][0], now.y + next[i][1], now.time + 1};
            if(!judge(temp)) continue;

            if(m[temp.x][temp.y] == aim) {
                startx = temp.x, starty = temp.y, tim = temp.time;
                return ;
            }
            book[temp.x][temp.y] = 1;
            q.push(temp);
        }
    }
}

int main()
{
    read_in();

    for(int i = 1; i <= k; i++) {
        memset(book, 0, sizeof(book));
        bfs(i + '0');
    }

    printf("%d\n", tim);

    return 0;
}

C++: #include<iostream>
#include<queue>
using namespace std;
int H,W,N,a,b,c,d,nh,nw;
int cost[1000][1000];
char t[1000][1000];
queue< int > qh;
queue< int > qw;
int th[4]={0,-1,0,1};
int tw[4]={1,0,-1,0};
int map[10][2];
int bfs(int tah,int taw){
  int h,w,ans;
  while(!qw.empty()){
    h=qh.front(),qh.pop();
    w=qw.front(),qw.pop();
    for(int i=0;i<4;i++){
      nh=h+th[i];
      nw=w+tw[i];
      if(0<=nh&&nh<H&&0<=nw&&nw<W){
	if(nh==tah&&nw==taw){
	  ans=cost[h][w]+1;
	  return ans;
	}else if(cost[nh][nw]==-1){
	  qh.push(nh);
	  qw.push(nw);
	  cost[nh][nw]=cost[h][w]+1;
	}
      }
    }
  }
}
void syokika(){
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(cost[i][j]!=-2)cost[i][j]=-1;
    }
  }
  while(!qh.empty()){
    qh.pop();
    qw.pop();
  }
}
int main(){
  cin>>H>>W>>N;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>t[i][j];
      if(t[i][j]=='S'){
	map[0][0]=i;
	map[0][1]=j;
      }else if(t[i][j]=='X'){
	cost[i][j]=-2;
      }else if(t[i][j]!='.'){
	map[t[i][j]-'0'][0]=i;
	map[t[i][j]-'0'][1]=j;
      }else{
	
      }
    }
  }
  int sum=0,a;
  for(int i=0;i<N;i++){
    syokika();

    qh.push(map[i][0]);
    qw.push(map[i][1]);
    cost[map[i][0]][map[i][1]]=0;
    a=bfs(map[i+1][0],map[i+1][1]);
    sum+=a;
  }
  cout<<sum<<endl;
  return 0;
}

C++: 			if(temp.x==p[i].x && temp.y==p[i].y)
			{
				step=use[temp.x][temp.y];
				result=result+step;
				flag=1;
				break;
			}

C++: 
#include<iostream>
#include<string>
#include<queue>
using namespace std;

#define INF 1000000000

string mem[4000], origin[4000];
char N;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, H, W, sx, sy, d[4000][4000];

int dfs(char p)
{
  for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++)
      d[i][j] = INF;
  queue<int> q;
  q.push(sx);
  q.push(sy);
  d[sy][sx] = 0;
  while(1)
  {
    int x = q.front(); q.pop();
    int y = q.front(); q.pop();
    if(mem[y][x] == p)
    {
      sx = x;
      sy = y;
      return d[y][x];
    }
    for(int i = 0; i < 4; i++)
    {
      int tx = x + dx[i], ty = y + dy[i];
      if(tx >= 0 && tx < W && ty >= 0 && ty < H && d[ty][tx] == INF && mem[ty][tx] != 'X')
      {
        q.push(tx);
        q.push(ty);
        d[ty][tx] = d[y][x] + 1;
      }
    }
   
  }
}

int main()
{
  cin >> H >> W >> N;
  sx = -1; sy = -1;
  for(int i = 0; i < H; i++)
  {
    cin >> mem[i];
    origin[i] = mem[i];
    if(sx != -1)
      continue;
    for(int j = 0; j < mem[i].length(); j++)
    {
      if(mem[i][j] == 'S')
      {
        sx = j;
        sy = i;
      }
    }
  }
  int ans = 0; 
  for(char i = '1'; i <= N; i++)
  {
    for(int j = 0; j < H; j++)
      mem[j] = origin[j];
    ans += dfs(i);
  }
  cout << ans << endl;
}