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++: // https://onlinejudge.u-aizu.ac.jp/problems/0558
// チーズ (Cheese)
// 一张地图上有开始点、空白、阻碍和奶酪
// 奶酪的数量N是1-9，其中有硬度1-9，初始只能吃1个硬度的然后2个、三个。
// 可以直接N次BFS也可以一直BFS（记录吃了几个）
// 如果硬度是随机的？dfs可能超时、bfs要记录地图变化就比较难写了

#include <cstring>
#include <iostream>
#include <map>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

char m[1100][1100];
char mark[1100][1100];
int W, H, N;
pii s[10];
pii dir[4] = {pii(-1, 0), pii(1, 0), pii(0, 1), pii(0, -1)};

int bfs(int n)
{
    memset(mark, 0, sizeof(mark));
    pii start = s[n];
    queue<pii> q;
    q.push(start);
    mark[start.first][start.second] = 1;
    int ans = 0;
    while (!q.empty())
    {
        ans++;
        int k = q.size();
        for (int i = 0; i < k; ++i)
        {
            for (int i = 0; i < 4; ++i)
            {
                pii t = q.front();
                t = pii(t.first + dir[i].first, t.second + dir[i].second);
                if (t.first >= 0 && t.second >= 0 && t.first < H && t.second < W && !mark[t.first][t.second])
                {
                    if (m[t.first][t.second] == '1' + n)
                    {
                        return ans;
                    }
                    else if (m[t.first][t.second] == '.' || m[t.first][t.second] >= '1' && m[t.first][t.second] <= '9')
                    {
                        q.push(t);
                        mark[t.first][t.second] = 1;
                    }
                }
            }
            q.pop();
        }
       
    }
    return 100; // unreachable code
}

int main()
{
    cin >> H >> W >> N;
    for (int i = 0; i < H; ++i)
    {
        cin >> m[i];
        for (int j = 0; j < W; ++j)
        {
            if (m[i][j] >= '1' && m[i][j] <= '9')
            {
                s[m[i][j] - '0'] = pii(i, j);
            }
            else if (m[i][j] == 'S')
            {
                m[i][j] = '.';
                s[0] = pii(i, j);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < N; ++i)
    {
        // cout << ans << endl;
        ans += bfs(i);
    }
    cout << ans << endl;
    return 0;
}

C++: #include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_HW = 1000;
int n, h, w, rat = 1, s[2], g[2], flag[MAX_HW][MAX_HW][2];
int town[MAX_HW][MAX_HW], save[1];
char town2[MAX_HW][MAX_HW];
queue <P> que;
P p;
void bfs(int sy, int sx){
	que.push(P(sy, sx));
	flag[p.first][p.second][1] = 0;
	while (que.size()){
	RE:
		p = que.front();
		que.pop();
		flag[p.first][p.second][0] = rat;
		for (int i = -1; i <= 1; i++){
			for (int j = -1; j <= 1; j++){
				if (i == 0 || j == 0){
					if (town2[p.first + i][p.second + j] != 'X'&&flag[p.first + i][p.second + j][0] != rat&&p.first + i < h&&p.first + i >= 0 && p.second + j < w&&p.second + j >= 0) {
						if (town[p.first + i][p.second + j] == rat){
							flag[p.first + i][p.second + j][1] = flag[p.first][p.second][1] + 1;
							if (rat == n) return;
							rat++;
							while (que.size()){
								que.pop();
							}
							que.push(P(p.first + i, p.second + j));
							goto RE;
						}
						flag[p.first + i][p.second + j][1] = flag[p.first][p.second][1] + 1;
						que.push(P(p.first + i, p.second + j));
					}
				}
			}
		}
	}
}
int main(){
	cin >> h >> w >> n;
	rat = 1;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			cin >> town2[i][j];
			town[i][j] = town2[i][j] - 48;
			if (town2[i][j] == 'S'){
				s[0] = i;
				s[1] = j;
			}
			if (town[i][j] == n){
				g[0] = i;
				g[1] = j;
			}
		}
	}
	bfs(s[0], s[1]);
	cout << flag[g[0]][g[1]][1] << endl;
	return 0;
}

C++: #include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;

char ma[1005][1005];int vis[1005][1005];
int w,h,n;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

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

void bfs(char ed)
{
    queue<node> que;
    que.push(start);
    vis[start.x][start.y]=1;
    while(!que.empty())
    {
        node no=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            int x=no.x+dx[i];
            int y=no.y+dy[i];
            cout<<x<<y<<endl;
            if(!vis[x][y]&&x<w&&x>=0&&y<h&&y>=0&&ma[x][y]!='X')
            {
                if(ma[x][y]==ed)
            {
                start.x=x;
                start.y=y;
                start.time=no.time+1;
                return ;
            }
            vis[x][y]=1;
            node no1;
            no1.x=x;no1.y=y;no1.time=no.time+1;
            que.push(no1);

            }

        }
    }
}

int main()
{
    while(~scanf("%d %d %d", & w, & h, & n))
    {
        for(int i=0;i<w;i++)
        {
            scanf("%s",&ma[i]);
            for(int j=0;j<h;j++)
                if(ma[i][j]=='S')
                {
                    start.x=i;
                    start.y=j;
                    start.time=0;
                }

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

            printf("%d\n",start.time);
    }
}

C++: #include <queue>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

#define INF (1 << 26)

const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int main()
{
	int H, W, N;

	cin >> H >> W >> N;

	vector<string> D(H);

	for (int i = 0; i < H; i++)
		cin >> D[i];

	int route = 0;

	for (int i = 1; i <= N; i++)
	{
		queue<pair<int, int> > que;

		vector<vector<int> > memo(H, vector<int>(W, INF));

		char start;

		if (i == 1)
		{
			start = 'S';
		}
		else
		{
			start = i + 48;
		}

		pair<int, int> start_;

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (D[i][j] == start)
				{
					start_.first = j;
					start_.second = i;
				}
			}
		}

		que.push(start_);

		memo[start_.second][start_.first] = route;

		while (que.size())
		{
			pair<int, int> place = que.front(); que.pop();

			int x, y;

			x = place.first;
			y = place.second;

			for (int dir = 0; dir < 4; dir++)
			{
				if (0 <= x + dx[dir] && x + dx[dir] < W && 0 <= y + dy[dir] && y + dy[dir] < H)
				{
					if (D[y][x] != 'X')
					{
						place.first = x + dx[dir];
						place.second = y + dy[dir];

						que.push(place);

						memo[y + dy[dir]][x + dx[dir]] = memo[y][x] + 1;

						if (D[y + dy[dir]][x + dx[dir]] - 48 == i)
						{
							route += memo[y][x] + 1;

							goto Exit;
						}
					}
				}
			}
		}

	Exit:;
	}

	cout << route << endl;

	return 0;
}