3096217_ac_1966ms_5264k.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 107 行

import java.util.*;

public class Main 
{
	static final int INF = 2100000000;

    public static void main(String [] args)
    {
		new Main().solve();
    }

	private void solve()
	{
		Scanner cin = new Scanner (System.in);

		int M, N, min;
		int st, ed;
		int i, j, k, cas;
		int dp[][] = new int [101][28];
		int from[][] = new int [101][28];
		String inf[] = new String [101];

		cas = 1;
		while(true)
		{
			M = cin.nextInt();
			N = cin.nextInt();
			if(M==0&&N==0)
			{
				break;
			}
			System.out.println("Case "+(cas++)+":\n");
			for(i = 1; i <= M; i++)
			{
				inf[i] = cin.next();
			}
			st = cin.nextInt();
			ed = cin.nextInt();
			for(i = 1; i <= M; i++)
			{
				Arrays.fill(dp[i],INF);
				Arrays.fill(from[i],-1);
			}
			ed--;
			for(j = 0; j < N; j++)
			{
				if(inf[ed].charAt(j)=='O')
				{
					dp[ed][j] = 1;
					from[ed][j] = -1;
				}
			}
			for(i = ed-1; i >= st; i--)
			{
				for(j = 0; j < N; j++)
				{
					if(inf[i].charAt(j)=='O')
					{
						min = INF;
						int prev = -1;;
						for(k = N-1; k >= 0; k--)
						{
							if(inf[i+1].charAt(k) == 'O' && dp[i+1][k] + (j!=k?1:0) <= min)
							{
								min = dp[i+1][k] + (j!=k?1:0);
								prev = k;
							}
						}
						if(min != INF)
						{
							dp[i][j] = min;
							from[i][j] = prev;
						}
					}
				}
			}
			int first = -1;
			min = INF;
			for(i = N-1; i >= 0; i--)
			{
				if(dp[st][i] <= min)
				{
					min = dp[st][i];
					first = i;
				}
			}
			if(min==INF)
			{
				System.out.println("Not available");
			}
			else
			{
				for(i = 0; i < min; i++)
				{
					System.out.print((char)(first+'A')+": "+st+'-');
					while(st<ed&&from[st][first]==first)
						st++;
					st++;
					System.out.println(st);
					first = from[st-1][first];
				}
			}
			System.out.println();
		}
	}
}